Skip to content
← All Patterns
← Bucket Sort / Top-KTwo Heaps →
Array & StringBeginner

Cyclic Sort

Place each number at its correct index (value i at index i) by swapping, to find missing or duplicate numbers in a range [0, n] or [1, n].

Problem: Find Missing Number

Given array [3,0,1] containing numbers in range [0, n], find the missing number.

i=0: nums[0]=3, correct index is 3

nums[0] = 3, which belongs at index 3. But array size is 3, so index 3 is out of bounds. Skip this element and move i forward.

Step 1/6
Speed:

When to Use

  • Array contains numbers in a known range [0, n] or [1, n]
  • Find missing, duplicate, or corrupt numbers
  • In-place rearrangement without extra space

Key Indicators

  • Numbers in range [0, n] or [1, n]
  • Find missing / duplicate number
  • In-place with O(1) extra space
  • Unsorted array of bounded integers

Complexity

Time

O(n)

Space

O(1)

Common Problems

Missing NumberFind All Numbers Disappeared in an ArrayFind All Duplicates in an ArrayFind the Duplicate NumberFirst Missing Positive

Code

i = 0
while i < n:
    correct = nums[i]  # or nums[i] - 1
    if nums[i] != nums[correct]:
        swap(nums[i], nums[correct])
    else:
        i += 1
# Now scan for index where nums[i] != i

Want all 29 patterns with detailed visual walkthroughs?

The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.

Book Coming Soon ($4.99)