Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on array fundamentals.
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 = [3,0,1]
Output: 2
Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation:
n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
Constraints:
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums are unique.Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Math · Binary Search · Bit Manipulation
[3,0,1]
[0,1]
[9,6,4,2,3,5,7,0,1]
first-missing-positive)single-number)find-the-duplicate-number)couples-holding-hands)find-unique-binary-string)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #268: Missing Number
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int ans = n;
for (int i = 0; i < n; ++i) {
ans ^= (i ^ nums[i]);
}
return ans;
}
}
// Accepted solution for LeetCode #268: Missing Number
func missingNumber(nums []int) (ans int) {
n := len(nums)
ans = n
for i, v := range nums {
ans ^= (i ^ v)
}
return
}
# Accepted solution for LeetCode #268: Missing Number
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return reduce(xor, (i ^ v for i, v in enumerate(nums, 1)))
// Accepted solution for LeetCode #268: Missing Number
impl Solution {
pub fn missing_number(nums: Vec<i32>) -> i32 {
let n = nums.len() as i32;
let mut ans = n;
for (i, v) in nums.iter().enumerate() {
ans ^= (i as i32) ^ v;
}
ans
}
}
// Accepted solution for LeetCode #268: Missing Number
function missingNumber(nums: number[]): number {
const n = nums.length;
let ans = n;
for (let i = 0; i < n; ++i) {
ans ^= i ^ nums[i];
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.