Missing Number | Leetcode 268 | Explained

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.

Here’s the [Problem Link] to begin with.

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.length
• 1 <= n <= 10⁴
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

BRUTE FORCE SOLUTION

1. What does the question says?

We have an array of integers named nums containing n distinct numbers taken from the set {0, 1, 2, …, n}. Out of these n + 1 possible numbers, exactly one is missing in the array. We need to identify which number from 0 to n is not present in nums and return it.

2. How do we approach the problem?

The provided approach uses a simple membership check for each candidate number:

1. We know that the missing number has to be some integer from 0 to n.
2. We check sequentially from i = 0 up to i = n whether i is not in the list nums.
3. Once we find such an i, we return it because it must be the missing number.

This method guarantees correctness because:

• By iterating from 0 to n, we cover all possible numbers in the required range.
• The first number that is not found in nums is, by definition, the missing one.

3. Code Implementation

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for i in range(0, len(nums) + 1):
            if i not in nums:
                return i

4. Step-by-Step Explanation

1. Loop Through Possible Numbers: Go from i = 0 up to i = len(nums) (inclusive).
2. Check Membership: For each i, we check if i is not present in the list nums.
3. Return If Absent: The moment we find i that doesn’t exist in nums, we return i as the missing number.

5. Dry Run

Let’s go through the code step by step, using images to illustrate the detailed dry run process.

6. Potential Edge Cases

1. Smallest Array:
   • If nums = [1] (n = 1), the missing number might be 0.
2. All Elements Present Except the Last:
   • If nums = [0, 1, 2, …, n-1], then the missing number is n.
3. Missing 0:
   • If nums = [1, 2, 3, …, n], return 0.
4. Already In Order:
   • Even if nums is sorted [0, 1, 2, 3, …, m-1, m+1, …, n], our logic still checks each number.

7. Time and Space Complexity

• Time Complexity:O(n²) in the worst case because:
  • We are iterating from 0 to n (which is n+1 iterations).
  • Each membership check (i not in nums) is O(n) for a list.
• Space Complexity: O(1), as we only use extra variables for iterating (i) and do not allocate significant additional space.

BETTER SOLUTION

1. What does the question says?

We have an array of integers named nums containing n distinct numbers taken from the set {0, 1, 2, …, n}. Out of these n + 1 possible numbers, exactly one is missing in the array. Our goal is to identify which number from 0 to n is missing and return it.

2. How do we approach the problem?

This approach uses a frequency map (dictionary) to keep track of which numbers appear in the array:

1. Create a dictionary freq where each key in the range [0 … n] is initialized to 0.
2. Iterate over the elements of nums and increment the corresponding value in freq.
3. Finally, check which key in freq remains at 0, meaning that number never appeared in nums. Return this key.

By doing so, we ensure every number that appears in nums is marked. The one that remains at a count of 0 is the missing number.

3. Code Implementation

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        freq = {i: 0 for i in range(0, len(nums) + 1)}
        for i in nums:
            freq[i] += 1
        for k, v in freq.items():
            if v == 0:
                return k

4. Step-by-Step Explanation

1. Initialize a dictionary freq with keys from 0 up to len(nums) (inclusive), each set to 0.
2. Traverse the list nums and increment freq[i] for each number i in nums.
3. Iterate over each key-value pair in freq. The first key (k) whose value (v) is 0 is the missing number, so return k.

5. Dry Run

Let’s go through the code step by step, using images to illustrate the detailed dry run process.

6. Potential Edge Cases

1. Smallest Array:
   • If nums = [1] (which means n = 1), the missing number is 0.
2. All Elements Present Except the Last:
   • If nums = [0, 1, 2, …, n-1], the missing number is n.
3. Missing 0:
   • If nums = [1, 2, 3, …, n], return 0.
4. Already In Order:
   • If nums is sorted [0, 1, 2, …, m-1, m+1, …, n], the dictionary will still capture the missing number.

7. Time and Space Complexity

• Time Complexity: O(n) to populate freq plus another O(n) to iterate over its items, which simplifies to O(2n) = O(n).
• Space Complexity: O(n) because we create a dictionary of size n+1.

OPTIMAL SOLUTION

1. What does the question say?

We have an array of integers named nums containing n distinct numbers taken from the set {0, 1, 2, …, n}. Out of these n + 1 possible numbers, exactly one is missing in the array. We need to figure out which number in the range 0 to n does not appear in nums.

2. How do we approach the problem?

This approach leverages the formula for the sum of the first n natural numbers:

1. We know that the sum of all integers from 0 to n is given by the formula:
   n × (n+1) / 2​
2. Therefore, if we compute this expected sum and then subtract the actual sum of the elements in nums, the difference will be the missing number.

This is a clever trick because it avoids checking each element individually—we just rely on simple arithmetic.

3. Implementation

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        original_total = (n * (n + 1)) // 2
        return original_total - sum(nums)

4. Step-by-Step Explanation

1. Calculate n as the length of nums.
2. Compute the expected sum of all numbers from 0 to n using the formula:
   (n x (n + 1)) // 2
3. Compute the actual sum of elements in nums using sum(nums).
4. Subtract the actual sum from the expected sum to get the missing number.

5. Dry Run

Example: Suppose nums = [3, 0, 1].

• n = 3, which means the numbers should be {0, 1, 2, 3}.
• Using the formula: original_total = (n x (n + 1)) // 2 = 6
• The actual sum of nums is 3 + 0 + 1 = 4.
• The missing number is 6 – 4 = 2.

Hence, the function returns 2.

6. Potential Edge Cases

1. Smallest Array:
   • If nums = [1] (n = 1), then the sum formula is (1*(1+1))//2 = 1, and sum(nums) = 1, so the missing number is 0.
2. Missing 0:
   • If nums = [1, 2, 3, …, n], the formula result minus sum(nums) will give 0.
3. Missing n:
   • If nums = [0, 1, 2, …, n-1], the difference will yield n.
4. Handling Larger n:
   • Since we only use arithmetic operations, even large n should pose no major issue (assuming no overflow constraints beyond standard Python integers).

7. Time and Space Complexity

• Time Complexity: O(n) to compute sum(nums). The arithmetic operations themselves are O(1).
• Space Complexity: O(1), since we only store a few numeric variables.

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.