easyBit ManipulationPure DSA~12 min
Missing Sequence ID
An ingest pipeline assigns dense sequence IDs 0..n to events, but exactly one ID never arrived. Find the missing ID without sorting and without extra memory proportional to n.
Problem
Given an array nums containing n distinct numbers drawn from the range [0, n], return the single number in that range that is missing from the array.
Input
An array nums of length n (1 ≤ n ≤ 10^4); values are distinct and in [0, n].
Output
An integer — the missing value.
Constraints
- Exactly one value in [0, n] is absent
- All present values are distinct
- Aim for O(n) time and O(1) extra space
Examples
Example 1
Input
nums = [3, 0, 1]
Output
2
Range is [0,3]; 2 is the only value not present.
Example 2
Input
nums = [0, 1]
Output
2
Range is [0,2]; the missing value is 2.