Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Cyclic Sort Pattern

You are given an array of N numbers. The array contains every value from 1 to N, but the values are in the wrong order.

[3, 1, 5, 4, 2]    becomes    [1, 2, 3, 4, 5]

A normal sorting algorithm can solve this in O(N log N) time. A second counting array can solve it in O(N) time, but it needs O(N) extra space.

This problem gives us a useful fact. Every value has one correct position:

  • 1 belongs at index 0.
  • 2 belongs at index 1.
  • A value v belongs at index v - 1.

We do not need to compare values to discover their order

.....

.....

.....

Like the course? Get enrolled and start learning!

Reading Progress

0%

Vote for new content