Skip to main content
Cyclic Sort

Find All Missing

After cyclic sort, every index where nums[i] ≠ i+1 represents a missing number. Collect all such indices. Handles multiple missing numbers in O(n).

O(n)
·
O(1)
say this out loud

Same 1-to-n correspondence, but I mark a value as seen by negating the element at that index, then every index still positive is a missing number.

How It Works

Finding all missing numbers extends cyclic sort's single-missing logic to any number of gaps. First pass: place each value at its home index, skipping a swap whenever the destination already holds the correct value (that means the value in hand is a duplicate crowding out something missing). Second pass: every index i where nums[i] does not equal i+1 marks a missing number, namely i+1.

Duplicates and missing values are two sides of the same coin here, each duplicate occupies the slot a missing number should fill. The whole procedure is O(n) time and O(1) auxiliary space (output aside), beating the O(n) extra memory of a hash-set diff while remaining a straightforward pair of linear scans.

Step-by-Step Visualization

nums [4, 3, 2, 7, 8, 2, 3, 1], eight slots holding values 1 to 8 with repeats. Find every number that never appears
i
4
0
3
1
2
2
7
3
8
4
2
5
3
6
1
7
length8
1/11

Code

Java
static List<Integer> findAllMissing(int[] nums) {
  int i = 0;
  while (i < nums.length) {
    int correct = nums[i] - 1;
    if (nums[i] != nums[correct]) {
      int tmp = nums[i]; nums[i] = nums[correct]; nums[correct] = tmp;
    } else i++;
  }

  List<Integer> missing = new ArrayList<>();
  for (int j = 0; j < nums.length; j++)
    if (nums[j] != j + 1) missing.add(j + 1);
  return missing;
}

Tips & Gotchas

1After cyclic sort, every index where nums[i] !== i+1 represents a missing number
2Collect all such indices
3Works for finding all missing numbers in range [1, n]

Practice Problems

  • 1Find All Numbers Disappeared in an Array
  • 2Find All Duplicates in an Array
  • 3First Missing Positive

About the Cyclic Sort Pattern

When an array contains numbers in the range [1, n] (or [0, n]), you can place each number at its 'correct' index (number i goes to index i-1). After sorting, any index without its correct number reveals the missing or duplicate value.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

  • Two Sum
  • Best Time to Buy & Sell Stock
  • Maximum Subarray
  • Merge Intervals
  • Product of Array Except Self
  • Container With Most Water

Frequently Asked Questions

How does the marking (negation) approach compare to cyclic sort here?

Negating nums[abs(v)-1] to mark 'value v seen' also runs in O(n)/O(1) and involves less swap choreography, so many prefer it for Disappeared Numbers. Cyclic sort generalizes better when the follow-up asks for duplicates and missing values simultaneously, since it fully normalizes positions.

Why does the swap loop skip when the destination already holds the right value?

If index v-1 already contains v, placing another v there gains nothing and the loop would swap the same pair forever. Skipping breaks the infinite loop and leaves the duplicate stranded at a wrong index. Exactly the signal the second pass reads as a missing number's slot.