Problem Description

You're given a sorted array of unique integers nums and a range defined by [lower, upper]. Your task is to find all the missing numbers in this range that are not present in nums, and represent them as a list of ranges.

The problem asks you to identify which numbers between lower and upper (inclusive) are missing from the array nums. Instead of listing each missing number individually, you need to group consecutive missing numbers into ranges represented as [start, end].

For example:

• If nums = [0, 1, 3, 50, 75] and the range is [0, 99]
• Missing numbers are: 2, 4-49, 51-74, 76-99
• The output would be: [[2, 2], [4, 49], [51, 74], [76, 99]]

The solution works by checking three key areas:

1. Before the first element: If nums[0] > lower, then all numbers from lower to nums[0] - 1 are missing
2. Between consecutive elements: For each pair of consecutive numbers in nums, if they differ by more than 1, the numbers between them are missing
3. After the last element: If nums[-1] < upper, then all numbers from nums[-1] + 1 to upper are missing

The pairwise function is used to iterate through consecutive pairs of elements in the array, making it easy to identify gaps. When a gap is found (i.e., b - a > 1), we add the range [a + 1, b - 1] to our answer.

The special case of an empty nums array is handled separately - in this case, the entire range [lower, upper] is missing.

Intuition

The key insight is that since nums is already sorted, we can identify missing ranges by looking at the "gaps" in the sequence. Think of it like walking along a number line from lower to upper - whenever we encounter a number from nums, we know it's not missing. The missing parts are the gaps where we "jump over" numbers.

To find these gaps systematically, we need to check three potential locations where missing numbers can occur:

1. The beginning gap: There might be missing numbers before we even reach the first element of nums. If nums starts at 5 but our range starts at 1, then [1, 4] is missing.

2. The middle gaps: Between any two consecutive numbers in nums, if they're not adjacent (like 3 and 7), then everything between them (4, 5, 6) is missing. We can detect this by checking if the difference between consecutive elements is greater than 1.

3. The ending gap: After processing all elements in nums, there might still be numbers missing at the end if nums ends before reaching upper.

The beauty of this approach is its simplicity - we're essentially doing a single pass through the array, checking the "boundaries" where missing ranges can occur. Since nums is sorted, we can process it sequentially without needing to jump around or use additional data structures.

The pairwise function elegantly handles the middle gaps by giving us each consecutive pair (a, b). If b - a > 1, we know [a+1, b-1] contains missing numbers. This avoids index manipulation and makes the code cleaner.

The edge case of an empty array becomes trivial - if there are no numbers in nums, then the entire range [lower, upper] is missing.

Solution Approach

The solution uses a simulation approach to directly identify and collect missing ranges. Here's how the implementation works:

Step 1: Handle Empty Array

if n == 0:
    return [[lower, upper]]

If nums is empty, the entire range [lower, upper] is missing, so we return it as a single range.

Step 2: Check for Missing Range Before First Element

if nums[0] > lower:
    ans.append([lower, nums[0] - 1])

If the first element in nums is greater than lower, there's a gap at the beginning. We add the range [lower, nums[0] - 1] to our answer list.

Step 3: Find Gaps Between Consecutive Elements

for a, b in pairwise(nums):
    if b - a > 1:
        ans.append([a + 1, b - 1])

The pairwise function generates consecutive pairs from nums. For each pair (a, b):

• If b - a > 1, there's a gap between them
• The missing range is [a + 1, b - 1]
• For example, if we have pair (3, 7), the difference is 4, so we add range [4, 6]

Step 4: Check for Missing Range After Last Element

if nums[-1] < upper:
    ans.append([nums[-1] + 1, upper])

If the last element is less than upper, there's a gap at the end. We add the range [nums[-1] + 1, upper] to complete our missing ranges.

The algorithm maintains a list ans to collect all missing ranges as we discover them. Since we process nums from left to right and add ranges in order, the resulting list is automatically sorted.

Time Complexity: O(n) where n is the length of nums, as we make a single pass through the array.

Space Complexity: O(1) for auxiliary space (not counting the output array), as we only use a constant amount of extra variables.

Example Walkthrough

Let's walk through a concrete example to see how the solution identifies missing ranges.

Example: nums = [2, 5, 6, 10], lower = 0, upper = 12

We need to find all missing numbers in the range [0, 12] that aren't in nums.

Step 1: Check if array is empty

• nums has 4 elements, so we continue.

Step 2: Check before first element

• First element is nums[0] = 2
• Since 2 > 0 (our lower bound), numbers 0 and 1 are missing
• Add range [0, 1] to our answer
• ans = [[0, 1]]

Step 3: Check gaps between consecutive elements

• Process pairs using pairwise:

  Pair (2, 5):

  • Difference: 5 - 2 = 3 which is > 1
  • Missing numbers are 3 and 4
  • Add range [3, 4] to answer
  • ans = [[0, 1], [3, 4]]

  Pair (5, 6):

  • Difference: 6 - 5 = 1 which equals 1
  • No gap here, 5 and 6 are consecutive
  • No range to add

  Pair (6, 10):

  • Difference: 10 - 6 = 4 which is > 1
  • Missing numbers are 7, 8, and 9
  • Add range [7, 9] to answer
  • ans = [[0, 1], [3, 4], [7, 9]]

Step 4: Check after last element

• Last element is nums[-1] = 10
• Since 10 < 12 (our upper bound), numbers 11 and 12 are missing
• Add range [11, 12] to answer
• ans = [[0, 1], [3, 4], [7, 9], [11, 12]]

Final Result: [[0, 1], [3, 4], [7, 9], [11, 12]]

This represents all the missing numbers: 0-1, 3-4, 7-9, and 11-12, which aren't present in the original array but fall within our specified range [0, 12].

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The algorithm performs the following operations:

• Checking if the array is empty: O(1)
• Checking if nums[0] > lower: O(1)
• Iterating through consecutive pairs using pairwise(nums): O(n-1) = O(n)
• Checking if nums[-1] < upper: O(1)

Since we traverse the array once through the pairwise iteration, the overall time complexity is O(n).

Space Complexity: O(1) (excluding the space required for the output array ans). The algorithm uses only a constant amount of extra space:

• Variable n to store the length: O(1)
• Variables a and b in the loop for storing pairs: O(1)

The pairwise function creates an iterator that yields consecutive pairs without creating additional data structures, so it doesn't require extra space proportional to the input size. If we include the output array ans, the space complexity would be O(k) where k is the number of missing ranges, but following the convention stated in the reference answer, we ignore the space consumption of the answer.

Common Pitfalls

1. Off-by-One Errors in Range Boundaries

One of the most common mistakes is incorrectly calculating the boundaries of missing ranges, especially when dealing with consecutive numbers.

Incorrect Implementation:

# Wrong: Including the existing numbers in the range
if nums[0] > lower:
    result.append([lower, nums[0]])  # Should be nums[0] - 1

# Wrong: Missing the +1 and -1 adjustments
for i in range(n - 1):
    if nums[i + 1] - nums[i] > 1:
        result.append([nums[i], nums[i + 1]])  # Should be [nums[i] + 1, nums[i + 1] - 1]

Why it's wrong: This would include numbers that actually exist in nums as part of the missing ranges. For example, if nums = [3, 7], the missing range between them is [4, 6], not [3, 7].

Correct Approach: Always remember to exclude the existing numbers by using nums[i] + 1 for the start and nums[i + 1] - 1 for the end of missing ranges.

2. Not Handling Edge Cases Properly

Pitfall Example:

def findMissingRanges(self, nums, lower, upper):
    result = []
  
    # Forgot to handle empty array case!
  
    # This will crash with IndexError if nums is empty
    if nums[0] > lower:
        result.append([lower, nums[0] - 1])
  
    # Rest of the code...

Solution: Always check for the empty array case first:

if len(nums) == 0:
    return [[lower, upper]]

3. Confusion Between Inclusive and Exclusive Ranges

Common Mistake: Treating the range as exclusive when it should be inclusive.

# Wrong: Thinking upper is exclusive
if nums[-1] < upper:
    result.append([nums[-1] + 1, upper - 1])  # Wrong! upper should be included

Correct Implementation: The problem specifies that both lower and upper are inclusive bounds, so:

if nums[-1] < upper:
    result.append([nums[-1] + 1, upper])  # Correct: upper is included

4. Using Wrong Comparison Operators

Pitfall:

# Wrong: Using >= instead of >
if nums[0] >= lower:  # This would miss the case when nums[0] == lower
    result.append([lower, nums[0] - 1])

When nums[0] == lower, there's no gap before the first element. Using >= would incorrectly create a range like [5, 4] when lower = 5 and nums[0] = 5.

Correct: Use strict inequality > to ensure there's actually a gap:

if nums[0] > lower:
    result.append([lower, nums[0] - 1])

5. Not Considering Single Missing Numbers

Some implementations try to optimize by treating single missing numbers differently from ranges, but this adds unnecessary complexity and potential for errors:

Overcomplicated:

# Unnecessary distinction between single numbers and ranges
if next_num - current == 2:
    result.append([current + 1])  # Single number as single-element list
else:
    result.append([current + 1, next_num - 1])  # Range

Better Approach: Treat all missing sections uniformly as ranges, even if they contain just one number:

if next_num - current > 1:
    result.append([current + 1, next_num - 1])  # Works for both single numbers and ranges

This keeps the output format consistent and the code simpler.