← Back to DSA Animator
Missing Number LC #268 Easy Binary Search · Sorted Array
Problem

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

Example 1
Input: nums = [0,1,3]
Output: 2
Explanation: After sorting: [0,1,3]. nums[2]=3 > 2=index → gap is to the left. Answer is 2.
Example 2
Input: nums = [0,1,2,3,4,5,6,7,9]
Output: 8
Example 3
Input: nums = [1,2,3]
Output: 0
Explanation: After sorting: [1,2,3]. nums[0]=1 > 0=index → gap is immediately to the left at index 0.
Constraints: n == nums.length  |  1 ≤ n ≤ 10⁴  |  0 ≤ nums[i] ≤ n  |  All numbers are unique.
Try Examples
Custom:
Sorted Array (Index vs Value)
nums[i] == i (value matches index) nums[i] > i (gap is to the LEFT) mid pointer missing gap
Gap Detector — nums[mid] vs mid
nums[mid]
—
vs
Waiting for first step…
mid
—
MISSING: ?
Variables
lo
—
hi
—
mid
—
nums[mid]
—
nums[mid] > mid?
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Sort the array. Set lo = 0, hi = nums.length.
2
Compute mid = lo + (hi - lo) / 2.
3
If nums[mid] > mid: gap is in the LEFT half → set hi = mid.
4
Else: gap is in the RIGHT half → set lo = mid + 1.
5
When lo == hi, that index is the missing number — return lo.
Time
O(n log n)
Space
O(1)
Why Binary Search Works

After sorting, if no number is missing before index i, then nums[i] == i. The missing number creates a shift: every element at or after the gap satisfies nums[i] == i + 1. This is a monotone predicate — perfect for binary search. nums[mid] > mid tells us the gap happened at or before mid, so we shrink the search space left. Otherwise it is strictly to the right.