Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Sliding Window
  • Two Pointers
  • Prefix Sum & Hash Map
  • Cyclic Sort
  • Merge Intervals
  • Monotonic Stack
Learn/Data Structures & Algorithms/Arrays & Strings

Cyclic Sort

6 min Intermediate 7 steps

Put each number in its own index and find what is missing.

n
4
Range
0..4
Goal
O(n), O(1)
01234031n + 1 possible values, n slots: exactly one is missing
current done skipped
In this lessonStep 1 of 7
  1. The problem
  2. Homes
  3. Full sort
  4. Missing
  5. Final scan
  6. Duplicates
  7. Recap
Step 1 / 7problem

Find the missing number

[4, 0, 3, 1] holds n = 4 distinct numbers from 0..4. Which one is missing?

A hash set costs O(n) space and sorting costs O(n log n). The values are in a known range, and that is the clue.

Key idea

Numbers in a range tied to the array length can index the array themselves.

←→ step·R replay·Space pause

You'll learn

  • Spot the known-range signal: values in 1..n or 0..n
  • Swap each value to its home index in O(n) and O(1) space
  • Find a missing number with a final scan
  • Compare values, not positions, to survive duplicates
Read the full notesArrays and Linked Lists, 6