MediumMedium Frequency20 min
Cyclic Sort
Sort arrays containing numbers in a given range in O(n) with no extra space.
When array values are in range [1..n], use cyclic sort to place each value at its correct index in O(n) time and O(1) space.
Cyclic Sort
Cyclic Sort — Step by Step
Find Missing Number
O(n)Each element swapped at most once → O(n) total. O(1) space vs O(n) for HashSet.Step-by-step1 / 5
i=0. nums[0]=3. Correct idx=2. Swap with nums[2]=5
nums[0]=3 → should be at index 2. nums[2]=5 Γëá 3. Swap.