Missing Number

Easy

Arista Networks

2 views

Topics:

ArraysBit Manipulation

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

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Missing Number

Easy

Arista Networks

2 views

Topics:

ArraysBit Manipulation

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

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the input array `nums`?
Is the input array guaranteed to contain only non-negative integers?
Is the input array guaranteed to contain `n` distinct numbers where `n` is the length of the array?
Can I assume the input array is not null or empty?
If the input is invalid in any way (e.g., contains numbers outside the range [0, n]), what should I return?

Brute Force Solution

Approach

We need to find a missing number in a sequence. The brute force approach tries every possible number within the expected range to see if it's the missing one.

Here's how the algorithm would work step-by-step:

Consider the smallest possible number in the range as the potential missing number.
Check if that number is present in the given set of numbers.
If it's present, then it is not the missing number, so move to the next number in the range.
If it is not present, then that number is the missing number; we can stop checking.
Repeat this process for every number in the expected range until you find the missing number.

Code Implementation

def find_missing_number_brute_force(numbers):
    expected_range_start = 0
    expected_range_end = len(numbers)

    for potential_missing_number in range(expected_range_start, expected_range_end + 1):

        # Check if the current number is present in the input list
        if potential_missing_number not in numbers:

            #If a number isn't present, we've found our missing number
            return potential_missing_number

    # If no number is missing from the range, it means 'n' is missing
    return expected_range_end + 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through a range of potential missing numbers, which can be up to n, where n is the number of elements in the input array plus one. For each potential missing number, it searches the input array to check for its presence. This search operation takes up to n steps. Therefore, in the worst case, we perform n searches, each potentially taking n steps, resulting in a time complexity of O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm checks each number in the expected range individually to see if it's present in the input sequence. It doesn't create any auxiliary data structures like lists, sets, or maps to store intermediate results or track visited elements. The algorithm uses a constant amount of extra space to store a potential missing number and possibly an iterator variable, irrespective of the input size N, where N is the number of elements in the input sequence. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem is to find a number missing from a sequence of consecutive numbers. The efficient approach avoids checking each possible number by cleverly using a mathematical formula.

Here's how the algorithm would work step-by-step:

Calculate the sum of all the numbers that *should* be in the sequence if no number were missing. You can do this using a simple formula.
Calculate the sum of the numbers that *are* actually present in the sequence.
Subtract the sum of the numbers present from the sum of the numbers that should be there. The result is the missing number.

Code Implementation

def find_missing_number(number_list):
    list_length = len(number_list)

    # Calculate the expected sum using the formula for the sum of an arithmetic series.
    expected_total = (list_length + 1) * (list_length + 2) // 2

    actual_total = sum(number_list)

    # Subtract the actual sum from the expected sum to find the missing number.
    missing_number = expected_total - actual_total

    return missing_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – Calculating the expected sum of the sequence requires a constant number of operations. Calculating the actual sum of the numbers present involves iterating through the input array of size n once. The subtraction to find the missing number is a constant time operation. Therefore, the dominant operation is the single iteration through the array, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm calculates two sums: the sum of the numbers that should be present and the sum of the numbers that are actually present. These sums are stored in single variables. No additional data structures that scale with the input size N are created. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
nums is null or empty	Return 0, as the missing number in an empty range [0, 0] is 0.
nums contains only one element (n=1)	Check if nums[0] is 0 or 1 and return the other value respectively.
nums contains all numbers from 0 to n, so the missing number is n+1 (integer overflow if n is close to MAX_INT)	The solution must avoid integer overflow when calculating the sum or expected sum and return n if all numbers from 0 to n-1 are present in nums.
nums contains only 0	Return 1, as the missing number is 1 when n = 1 and nums[0] = 0.
nums contains all numbers except 0	Return 0, as 0 is the missing number.
Large input array affecting time and space complexity	Ensure the chosen algorithm has optimal time complexity (O(n) preferably) and consider space constraints.
n is close to Integer.MAX_VALUE which may cause overflow in sum calculations	Utilize XOR operation or Gauss' Formula (n*(n+1))/2 cautiously, addressing possible overflow.
nums contains duplicate numbers (although problem states distinct numbers)	The solution should still function correctly, for example, XOR handles duplicates by canceling out pairs.