LeetCode DSA Series #6: 268. Missing Number

Source: Dev.to

Problem Overview

The task is LeetCode problem 268. Missing Number – given an array nums containing n distinct numbers taken from the range [0, n], find the one number that is missing from the array.

The problem is classified as Easy.

Approach 1 – Set Difference

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)

        # Build the full sequence [0, n] and convert to a set
        full_set = set(range(n + 1))

        # The missing number is the element present in full_set but not in nums
        missing = full_set - set(nums)
        return missing.pop()

Complexity

• Time: O(n) – building the set and computing the difference each scan the list once.
• Space: O(n) – extra set of size n + 1.

Approach 2 – Brute‑Force Search

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)

        # Check each number from 0 to n; return the first one not in nums
        for i in range(n + 1):
            if i not in nums:
                return i

Complexity

• Time: O(n²) in the worst case because i not in nums performs a linear search for each i.
• Space: O(1).

Approach 3 – List Removal

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)

        # Start with the full list [0, n] and remove each element found in nums
        sequence = list(range(n + 1))
        for num in nums:
            sequence.remove(num)
        return sequence[0]

Complexity

• Time: O(n²) – list.remove is O(n) and is called n times.
• Space: O(n) – the auxiliary list sequence.

Better Solutions

1. XOR Method (O(n) time, O(1) space)

The XOR of a number with itself is 0, and XOR is commutative. XOR all indices 0…n with all elements in nums; the result is the missing number.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)          # start with n (the extra index)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

Complexity

• Time: O(n) – single pass.
• Space: O(1) – only a few integer variables.

2. Summation Formula (O(n) time, O(1) space)

The sum of the first n natural numbers is n*(n+1)//2. Subtract the sum of the array from this total to obtain the missing number.

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

Complexity

• Time: O(n) – one pass to compute sum(nums).
• Space: O(1).

Both the XOR and summation approaches outperform the set‑based method in terms of constant‑factor performance while maintaining linear time and constant extra space.