Missing Numbers

Tags

Missing Numbers

Category

Arrays

Difficulty

Medium

Problem Statement

Given an array of distinct integers that should contain all numbers from 1 to n+2 (where n is the length of the array), but is missing exactly two numbers, find and return those two missing numbers in sorted order.

Intuition

The sum of 1 to n+2 is known. Subtracting the array's sum gives us the sum of the two missing numbers. Their average divides the full range into two halves, and exactly one missing number falls in each half. We can compute the expected sum of one half, subtract the actual values in that half, and derive both missing numbers.

Approach

  1. Let total = n + 2 where n = length(array).
  2. Compute expectedSum = total * (total + 1) / 2.
  3. Compute arraySum = sum of all elements in array.
  4. missingSum = expectedSum - arraySum (sum of the two missing numbers).
  5. midpoint = missingSum / 2 (integer division). One missing number is at most midpoint, the other is greater.
  6. Compute the expected sum of numbers from 1 to midpoint and the actual sum of array elements that are at most midpoint.
  7. firstMissing = expectedSumOfLeftHalf - actualSumOfLeftHalf.
  8. secondMissing = missingSum - firstMissing.
  9. Return [firstMissing, secondMissing].

Pseudocode

function missingNumbers(array):
    total = length(array) + 2
    expectedSum = total * (total + 1) / 2
    arraySum = sum(array)
    missingSum = expectedSum - arraySum

    midpoint = missingSum / 2    // integer division

    expectedLeftSum = midpoint * (midpoint + 1) / 2
    actualLeftSum = 0
    for num in array:
        if num <= midpoint:
            actualLeftSum += num

    firstMissing = expectedLeftSum - actualLeftSum
    secondMissing = missingSum - firstMissing

    return [firstMissing, secondMissing]

Time & Space Complexity

  • Time: O(n) — two passes through the array (one for total sum, one for left-half sum, or combined into one).
  • Space: O(1) — only a constant number of variables.

Key Insights

  • The midpoint partitioning guarantees that the two missing numbers fall into different halves, allowing us to isolate each one.
  • Integer division for the midpoint works because the two missing numbers are distinct, so their average is not an integer boundary issue — one is strictly below or equal to the midpoint and the other is strictly above.
  • An alternative approach using XOR bit manipulation also achieves O(n) time and O(1) space.

Edge Cases

  • The two missing numbers are consecutive (e.g., 3 and 4).
  • The missing numbers are 1 and total (the extremes).
  • Array is empty (length 0): both missing numbers are 1 and 2.
  • Large values of n: ensure no integer overflow in sum calculations.

Linked mentions