Coding Interview PatternsFind All Numbers Disappeared in an Array
EasyCyclic Sort

Find All Numbers Disappeared in an Array

Explanation & Solution

Practice Problem

Description

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range `[1, n]` that do not appear in nums.

Input:nums = [4, 3, 2, 7, 8, 2, 3, 1]
0
4
1
3
2
2
3
7
4
8
5
2
6
3
7
1
Output:[5, 6]
0
5
1
6

Explanation: n = 8, range is [1, 8]. The numbers 5 and 6 are missing.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n

Approach

Cyclic Sort pattern

1. Phase 1 — Cyclic Sort

  • Place each number at its correct index: nums[i] belongs at index nums[i] - 1
  • If nums[i] !== nums[j] (where j = nums[i] - 1), swap nums[i] with nums[j]
  • If they are equal — meaning nums[i] is already at the right place OR it's a duplicate — advance i
  • After this phase, every number that can be uniquely placed is at its correct index

2. Why Duplicates Are Handled Correctly

  • When two copies of the same number exist, the condition nums[i] === nums[j] catches it
  • We advance i, leaving the duplicate in place — it will mark its index as "wrong" in Phase 2

3. Phase 2 — Identify Missing Numbers

  • Scan the sorted array: index k should hold value k + 1
  • If nums[k] !== k + 1, then k + 1 is a missing number — add it to the result

🧠 Key Insight

  • The key insight: after cyclic sort, every index that holds the wrong value reveals a missing number at that position
Time
O(n)each element is moved at most once in Phase 1, and Phase 2 is a single scan
Space
O(1) auxiliary (output array excluded) — the sort is done in-place

Visualization

Input:
[4, 3, 2, 7, 8, 2, 3, 1]
4031227384253617
—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone
19 steps

Solution Code

Previous
Missing Number
Next
Find All Duplicates in an Array