Coding Interview PatternsMissing Number
EasyCyclic Sort

Missing Number

Explanation & Solution

Practice Problem

Description

Given an array nums containing n distinct numbers in the range [0, n], return the one number in the range that is missing from the array.

Input:nums = [3, 0, 1]
0
3
1
0
2
1

Output: 2

Explanation: n = 3, range is [0, 3]. The number 2 is missing.

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique

Approach

Cyclic Sort pattern

1. Cyclic Sort — Place Each Number at Its Index

  • For this problem, number x belongs at index x (not x - 1, since range starts at 0)
  • Compute j = nums[i] — that's where nums[i] should go
  • If nums[i] < n and nums[i] !== nums[j], swap nums[i] with nums[j]
  • If nums[i] >= n (the number n has no valid index), skip and advance i

2. Why Skip When nums[i] >= n?

  • The range is [0, n] but the array only has n slots (indices 0 to n-1)
  • The value n cannot be placed at any index in the array, so we leave it and move on

3. Scan for the Missing Number

  • After sorting, iterate through indices 0 to n-1
  • The first index k where nums[k] !== k is the missing number
  • If all positions match, the missing number is n (it was never placeable)

🧠 Key Insight

  • The cyclic sort approach avoids the common XOR or sum formula tricks, making the logic easy to visualize and extend to related problems (find all missing numbers, find duplicates, etc.)
Time
O(n)each element is moved at most once
Space
O(1)in-place sorting, no hash map needed

Visualization

Input:
[3, 0, 1]
300112
—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone
9 steps

Solution Code

Previous
Cyclic Sort
Next
Find All Numbers Disappeared in an Array