Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Cyclic Sort

Editorial

Every value has a home

A teacher gets back a pile of 30 exam papers, numbered 1 to 30, in no order at all. Sorting them doesn't take a single comparison: paper 17 goes in slot 17, whatever is around it. The number on each paper is the address of its slot.

Arrays get questions like that all the time. First Missing Positive: the smallest positive number that isn't in the array. Find All Duplicates in an Array: values 1 to n, some twice, which ones? The catch is the limit that usually comes with them: O(n) time and O(1) extra space. Sorting costs O(n log n). A hash set, or a counting array of size n, costs O(n) extra space.

But when the values are 1 to n and there are n slots, every value already has a place to live. In slots 0 to n − 1, the value v belongs at index v − 1. Send each value home, and the array itself becomes the record of what's there. That's cyclic sort.

Five values, 3, 1, 5, 4, 2, in a row of slots 0 to 4, with an arrow from each value down to its home in a second row: 3 to slot 2, 1 to slot 0, 5 to slot 4, 4 to slot 3, 2 to slot 1. Each slot of the second row is labelled with the value that lives there, so the second row reads 1, 2, 3, 4, 5.

Send it home

Walk the slots from the left. At slot i, look at the value v sitting there:

  • if v is in 1 to n and its home, slot v − 1, doesn't already hold a v, swap it home. Whatever was in slot v − 1 lands at slot i, so look at slot i again;
  • otherwise move on. There are three ways a value can't move: it's already home (v = i + 1), it has no home (below 1 or above n), or it's a copy whose home already holds the same value.

Do it yourself below. Tap any value to send it home, in any order you like. The widget refuses values that can't move and says why, counts your swaps against the values you've placed, and, when nothing else can move, asks you to read the answer.

Send It Home: send each value to its home slot, then read the first slot that isn't right

There's a loop inside a loop here, and it's still O(n). Each swap puts at least one value in its home, and the check nums[v - 1] != v means a slot that holds its own value is never touched again. Only n values can ever be home, so there are at most n swaps in the whole run, plus the n steps of i: O(n) time, O(1) extra space.

The order you choose doesn't change the outcome. The widget's list, [7, 3, 1, -2, 3, 2, 9], can be sent home in 48 different orders, counted on the judge. Every one of them took exactly 4 swaps, and every one ended with 1, 2, 3 and 7 at home and slot 3 as the first slot without its own value.

First Missing Positive

Why does the first wrong slot give the answer? n slots can hold at most the n values 1 to n. If they're all there, the smallest missing positive is n + 1. If not, the smallest absent value is at most n, and after sending everything home, slot i is wrong exactly when i + 1 is absent. So scan for the first wrong slot, and if there isn't one, answer n + 1. Negatives, zeros, values above n and copies can never be the answer, which is why they're allowed to sit anywhere.

First Missing Positive on [3, 4, -1, 1] — i walks the slots; a swap sends a value to its home. Then a scan finds the first slot that doesn't hold its own value.

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        // send nums[i] home while it has one (1 to n) and its home doesn't already hold it
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
            swap(nums[i], nums[nums[i] - 1]);
    }
    for (int i = 0; i < n; i++)
        if (nums[i] != i + 1) return i + 1;        // the first slot without its own value
    return n + 1;                                  // 1 to n are all there
}

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        # send nums[i] home while it has one (1 to n) and its home doesn't already hold it
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            v = nums[i]                         # read v first: the swap changes nums[i]
            nums[i], nums[v - 1] = nums[v - 1], v
    for i in range(n):
        if nums[i] != i + 1:                    # the first slot without its own value
            return i + 1
    return n + 1                                # 1 to n are all there

static int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        // send nums[i] home while it has one (1 to n) and its home doesn't already hold it
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int v = nums[i];
            nums[i] = nums[v - 1];
            nums[v - 1] = v;
        }
    }
    for (int i = 0; i < n; i++)
        if (nums[i] != i + 1) return i + 1;        // the first slot without its own value
    return n + 1;                                  // 1 to n are all there
}

function firstMissingPositive(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        // send nums[i] home while it has one (1 to n) and its home doesn't already hold it
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            const v = nums[i];
            nums[i] = nums[v - 1];
            nums[v - 1] = v;
        }
    }
    for (let i = 0; i < n; i++)
        if (nums[i] !== i + 1) return i + 1;       // the first slot without its own value
    return n + 1;                                  // 1 to n are all there
}

Each prints 3, 2, 1, 4, 3, 2 and 1 for [1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12], [1, 2, 3], [2, 1], [1, 1] and [0, -5, 2, 2, 3]. The Python version reads v before swapping, and the Java and JavaScript ones use a temporary for the same reason: the swap changes nums[i], so its old value has to be saved first.

Other answers in the same slots

Once every value is home, the array is a report. A slot i that doesn't hold i + 1 means i + 1 is missing, and the value sitting there is a copy of something. Each problem in the family just reads that report differently. Here's the placement on its own:

def send_home(nums):
    """Cyclic sort: every value 1..n that's in nums ends at index v - 1."""
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            v = nums[i]
            nums[i], nums[v - 1] = nums[v - 1], v

Find Missing and Repeated Values gives an n × n grid holding 1 to n², with one value twice and one missing. Read the grid row by row as one array of n² slots (cell (r, c) is index r · n + c, the address rule from Introduction to Arrays), send everything home, and the one wrong slot names both:

def find_missing_and_repeated_values(grid):
    nums = [v for row in grid for v in row]     # n x n values 1..n², read row by row
    send_home(nums)
    for i, v in enumerate(nums):
        if v != i + 1:                          # the one wrong slot: i + 1 is missing, v is the copy
            return [v, i + 1]

It returned [9, 5] for [[9, 1, 7], [8, 9, 2], [3, 4, 6]] and [2, 4] for [[1, 3], [2, 2]].

Find All Duplicates in an Array has values 1 to n, each once or twice. Every wrong slot holds a second copy:

def find_duplicates(nums):
    send_home(nums)
    return [v for i, v in enumerate(nums) if v != i + 1]   # each wrong slot holds a second copy

Sorted, it returned [2, 3], [1] and [] for [4, 3, 2, 7, 8, 2, 3, 1], [1, 1, 2] and [1].

Two more fit the same picture. Find All Numbers Disappeared in an Array wants every i + 1 whose slot is wrong. Missing Number has the values 0 to n in n slots: the home of v is index v, and n has no home (its sum formula from Introduction to Arrays is simpler there, but cyclic sort works too).

Marking instead of moving. The array can record what's there without reordering anything: for each value v, make the number at index |v| − 1 negative. The indexes still positive at the end are the missing values. It's the same O(n) time and O(1) space, and Frequency Counting with Hash Maps uses it for Find All Numbers Disappeared in an Array.

Spotting it

Clues for cyclic sort:

  • the values are 1 to n, or 0 to n, in an array of about n slots;
  • the question is about what's missing, repeated, or out of place;
  • the limit says O(n) time and O(1) extra space, and you're allowed to change the array.

And the near-misses:

  • The array must not change. Find the Duplicate Number forbids it, so it needs another idea (Floyd's cycle detection, from the linked list section, or binary search on the value).
  • The values aren't tied to positions (any integers, or a range much bigger than n): there are no homes, so use a hash set (Hashing).
  • The array is sorted and you want the k-th missing value: binary search does it in O(log n).

Common mistakes

if instead of while. One swap per slot

The value that lands at slot i after a swap never gets sent home. On [3, 4, -1, 1] the slots ended as [-1, 1, 3, 4], so the scan returned 1, though 1 is in the array. The answer is 2.

Python's one-line swap. nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]

Python assigns left to right: it changes nums[i] first, then works out nums[i] - 1 from the new value and writes to the wrong slot. On [2, 1] it swapped nothing, forever: the run hit the time limit. Read v = nums[i] first.

Dropping either check. while nums[i] != i + 1 or no 1 <= nums[i] <= n

Without "its home already holds it", two copies swap with each other forever: [1, 1] hit the time limit. Without the range check, Python's negative indexes turn −1 into a real slot, and [3, 4, -1, 1] hit the time limit too (C++ and Java would read outside the array instead).

Returning n when every slot is right.

[1, 2, 3] returned 3. If 1 to n are all there, the answer is n + 1: here, 4.

Check yourself

Quiz

1 / 6

Multiple choice

In an array of 7 slots, where does the value 5 belong?

Practice problems

From easier to harder:

  1. Find Missing and Repeated Values: read the grid as one array, then the one wrong slot.
  2. Find All Duplicates in an Array: every wrong slot holds a copy.
  3. First Missing Positive: values with no home, copies, and the n + 1 case.

Two more from earlier sections fit too: Missing Number (Array Basics) and Find All Numbers Disappeared in an Array (Hashing).

Next: Majority Element and Boyer–Moore Voting.