How do you solve Missing Number on LeetCode?

Missing Number (LeetCode #268) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The range of numbers is always from 0 to n, which allows for a simple mathematical solution.

What is the brute force solution for Missing Number?

The brute force approach for Missing Number is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach checks each number in the range [0, n] to see if it exists in the array. If it doesn't, that's the missing number. It's straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Missing Number?

Always consider edge cases, such as the smallest and largest possible inputs. Explain your thought process clearly as you work through the problem. If you get stuck, think about different ways to represent the data, like using a set or mathematical properties.

What are common mistakes when solving Missing Number?

Forgetting to account for the case when the missing number is n. Not using the properties of arithmetic sums to simplify the problem.

#268

Missing Number

Easy

ArrayHash TableMathBinary SearchBit ManipulationSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses the mathematical property of the sum of the first n natural numbers to find the missing number. This is efficient and uses minimal space.

⚙️

Algorithm

3 steps

1Step 1: Calculate the expected sum of numbers from 0 to n using the formula n * (n + 1) / 2.
2Step 2: Calculate the actual sum of the numbers in the array.
3Step 3: The missing number is the difference between the expected sum and the actual sum.

solution.py5 lines

1def missingNumber(nums):
2    n = len(nums)
3    expected_sum = n * (n + 1) // 2
4    actual_sum = sum(nums)
5    return expected_sum - actual_sum

ℹ

Complexity note: The time complexity is O(n) because we need to iterate through the array once to calculate the actual sum. The space complexity is O(1) since we are using a constant amount of space.

1The range of numbers is always from 0 to n, which allows for a simple mathematical solution.
2Using the sum formula reduces the problem to a single pass through the array.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.