How do you approach Missing Number?

The sum of numbers from 0 to n is n*(n+1)/2.

What is the time complexity of Missing Number?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Missing Number?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

Sitelet https://gitgood.dev/coding/missing-number

gitGood.dev

← Back to problems

Missing Number

EasyAlgorithms

Description

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.

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.

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.

Constraints

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

Missing Number: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 6 test cases (3 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

The sum of numbers from 0 to n is n*(n+1)/2.
Subtract the sum of the array from the expected sum.
Alternatively, use XOR: XOR all indices and all values together.

The optimal approach

Show the approach: Solution 1: Math (Sum Formula)

Calculate expected sum n*(n+1)/2 and subtract actual sum.

Solution 2: XOR

XOR all indices [0, n] with all array values. Pairs cancel, leaving the missing number.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.

← Back to problems

Missing Number

EasyAlgorithms

Description

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.

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.

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.

Constraints

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

Missing Number: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 6 test cases (3 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

The sum of numbers from 0 to n is n*(n+1)/2.
Subtract the sum of the array from the expected sum.
Alternatively, use XOR: XOR all indices and all values together.

The optimal approach

Show the approach: Solution 1: Math (Sum Formula)

Calculate expected sum n*(n+1)/2 and subtract actual sum.

Solution 2: XOR

XOR all indices [0, n] with all array values. Pairs cancel, leaving the missing number.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.