Leetcode – Missing Number Solution in Python

Spread the love

Introduction

The Missing Number problem is an elementary and widely-used problem in coding interviews. This problem tests one’s ability to recognize patterns and come up with efficient algorithms. In this extensive article, we will take a deep dive into the Missing Number problem on LeetCode, discuss multiple strategies to solve it, and analyze their time and space complexities with Python implementations.

Problem Statement

The problem can be stated as follows:

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.

Input

  • nums: a list of n integers, where 0 <= nums[i] <= n (0 <= n <= 10^4)

Output

  • Return the only number in the range [0, n] that is missing from the array.

Approach 1: Using Mathematical Formula

The sum of the first n natural numbers is given by the formula n*(n+1)/2. We can find the sum of all numbers from 0 to n and subtract the sum of the numbers present in the array. The result will be the missing number.

  1. Calculate the sum of the first n natural numbers using the formula n*(n+1)/2.
  2. Calculate the sum of the elements in the array.
  3. Subtract the sum of the elements in the array from the sum of the first n natural numbers. The result is the missing number.
def missingNumber(nums):
    n = len(nums)
    # Sum of first n natural numbers
    total_sum = (n * (n + 1)) // 2
    # Sum of elements in the array
    array_sum = sum(nums)
    # Missing number
    return total_sum - array_sum

Time Complexity

The time complexity is O(N) due to the summation of the array elements.

Space Complexity

The space complexity is O(1), as we only use a constant amount of additional space.

Approach 2: Using XOR

The XOR operation can also be used to find the missing number. This is based on the fact that a ^ a = 0 and a ^ 0 = a. Additionally, XOR satisfies the associative and commutative properties.

  1. Initialize an XOR sum as the length of the array.
  2. Iterate through the array, and for each index i, calculate the XOR sum of the index, the element at that index, and the current XOR sum.
  3. The final XOR sum is the missing number.
def missingNumber(nums):
    xor_sum = len(nums)
    for i, num in enumerate(nums):
        xor_sum ^= i ^ num
    return xor_sum

Time Complexity

The time complexity is O(N) because we iterate through the array once.

Space Complexity

The space complexity is O(1), as we only use a constant amount of additional space.

Approach 3: Using Sorting

We can also solve this problem by sorting the array first. After sorting, we can iterate through the array and find the first number that does not equal its index, which is the missing number.

  1. Sort the array.
  2. Iterate through the sorted array. If the number at index i is not equal to i, return i.
  3. If no missing number is found in the loop, the missing number is n.
def missingNumber(nums):
    nums.sort()
    for i, num in enumerate(nums):
        if i != num:
            return i
    return len(nums)

Time Complexity

The time complexity is O(N log N) due to the sorting operation.

Space Complexity

The space complexity is O(1) if the sorting is done in-place, or O(N) if a separate sorted array is used.

Conclusion

In this article, we thoroughly analyzed the Missing Number problem on LeetCode and explored three different approaches to solve it – using a mathematical formula, using XOR, and using sorting. The mathematical and XOR approaches are the most efficient in terms of time complexity and are highly recommended for solving this problem.

Leave a Reply