Cyclic Sort

This problem pattern introduces a particular sorting method that works when we have each of the numbers from $0$ to $n-1$ in an array of length $n$ . In general, this method works with any array of unsorted consecutive numbers!

Now consider the following problem:

Write a function cyclicSort(nums) that sorts the numbers in the array of integers nums. This array of length $n$ always contains each number from $0$ to $n-1$ . Do this using constant memory $O(1)$ and the best run-time possible.

Example:

input: nums = [5,1,2,3,8,7,4,0,9,6]
correct output: [0,1,2,3,4,5,6,7,8,9]

The optimal solution is in $O(n)$ runtime. We cannot do better than this because we have to at least look at every element to sort it. We can sort by starting at the beginning of the array, looking at the value of the element, and swapping our current element with the element that has an index equal to the current elements value. We do not move forward in the array until the swap results in our current element having index equal to value.

Let’s see how this works on our example input: [5,1,2,3,8,7,4,0,9,6]

swap 5 with 7 → [7,1,2,3,8,5,4,0,9,6] → do not move forward because nums[0] ≠ 0
swap 7 with 0 → [0,1,2,3,8,5,4,7,9,6] → move forward because nums[0] = 0
no swap → [0,1,2,3,8,5,4,7,9,6] → move forward because nums[1] = 1
no swap → [0,1,2,3,8,5,4,7,9,6] → move forward because nums[2] = 2
no swap → [0,1,2,3,8,5,4,7,9,6] → move forward because nums[3] = 3
swap 8 with 9 → [0,1,2,3,9,5,4,7,8,6] → do not move forward because nums[4] ≠ 4
swap 9 with 6 → [0,1,2,3,6,5,4,7,8,9] → do not move forward because nums[4] ≠ 4
swap 6 with 4 → [0,1,2,3,4,5,6,7,8,9] → move forward because nums[4] = 4
no swap → [0,1,2,3,4,5,6,7,8,9] → do not move forward because nums[4] ≠ 4
continue to move forward with no swaps until the end of the array since everything is now in order → [0,1,2,3,4,5,6,7,8,9]

Notice that the maximum total amount of swaps we can do is $n$ since we only swap elements that are out of order, and each swap places at least one more element in the correct order. We also do n work iterating from the start to the end of the array. hence $O(n+n)=O(2n)\in O(n)$ .

Note: We can make some small adjustments to this algorithm to deal with the following and not lose our runtime or memory efficiency:

a constant number of missing numbers from the consecutive number range.
a constant number of duplicates.

You have the chance to think about and practice these adjustments in the problems this week!!

Problems for this Week

(easy) missing-number

Given an array numscontaining ndistinct numbers in the range [0, n], return the only number in the range that is missing from the array. #268

(easy) find-all-numbers-disappeared-in-an-array

Given an array numsof nintegers where nums[i]is in the range [1, n], return an array of all the integers in the range[1, n]that do not appear innums #448

(medium) find-all-duplicates-in-an-array

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice. You must write an algorithm that runs in O(n) time and uses only constant extra space. #442

(medium) find-the-duplicate-number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1,n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space. #287

(hard) first-missing-positive

Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space. #41

(easy) kth-missing-positive-number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k. Return the kth positive integer that is missing from this array. #1539

Note: Actually, the fastest way to do this is with binary search $O(log(n))$