Place each number in [1..N] at its correct index arr[i] = i+1 in O(N) time and O(1) extra space.

Data Flow

input:  [3, 1, 5, 4, 2]

i=0: 3 -> swap with arr[2]   -> [5, 1, 3, 4, 2]
i=0: 5 -> swap with arr[4]   -> [2, 1, 3, 4, 5]
i=0: 2 -> swap with arr[1]   -> [1, 2, 3, 4, 5]
i=1..4: in order -> done

When to use

• Array of integers in range [1..N] (or [0..N-1]).
• Need to find duplicates / missing number(s) in O(1) extra space.

Code

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        j = nums[i] - 1          # target index
        if nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    return nums

Pitfalls

• Infinite loop when there are duplicates — the if nums[i] != nums[j] guard is mandatory.
• Off-by-one when input range is [0..N-1] instead of [1..N]. Target index becomes j = nums[i].

Analogy

Re-shelving numbered books back to their correct positions one swap at a time.

Interview tip: Whenever N == len(nums) AND every number fits in [1..N], cyclic sort is the intended O(N)/O(1) trick.