Problem Description

You have an array nums of length n (0-indexed, meaning positions go from 0 to n-1), and you're given a list of ranges that cover some portions of this array. Each range is defined by two values: a start position (inclusive) and an end position (inclusive).

Your task is to find all the gaps (uncovered portions) in the array that are not covered by any of the given ranges.

Key requirements:

• Find all uncovered ranges that are maximal (meaning they should be as large as possible)
• Each uncovered cell should belong to exactly one uncovered range
• Adjacent uncovered ranges should be merged (there shouldn't be two ranges where one ends at position r and the next starts at position r+1)
• Return the uncovered ranges sorted by their starting positions in ascending order

Example to illustrate: If n = 10 (array positions 0-9) and you have ranges [[1,3], [5,7]]:

• Position 0 is uncovered
• Positions 1-3 are covered by the first range
• Position 4 is uncovered
• Positions 5-7 are covered by the second range
• Positions 8-9 are uncovered

The uncovered ranges would be: [[0,0], [4,4], [8,9]]

The solution works by:

1. Sorting the given ranges by their start positions
2. Tracking the last covered position as we iterate through the sorted ranges
3. Whenever there's a gap between the last covered position and the start of the next range, that gap is an uncovered range
4. After processing all ranges, checking if there's an uncovered portion at the end of the array

Intuition

The key insight is to think about this problem as walking along a number line from position 0 to n-1, and identifying the gaps between covered regions.

Imagine you're painting segments on a wall. Some segments are already painted (the given ranges), and you need to find all the unpainted segments. The natural approach is to walk from left to right and note down each unpainted section you encounter.

To make this process efficient, we first sort the ranges by their starting positions. This allows us to process them in order from left to right, making it easy to identify gaps.

As we traverse through the sorted ranges, we maintain a variable last that tracks the rightmost position we've covered so far. This is crucial because:

• If a new range starts at position l and our last covered position is less than l-1, then positions [last+1, l-1] form an uncovered gap
• When ranges overlap, we need to update last to be the maximum of the current last and the end of the current range (this handles overlapping ranges correctly)

The beauty of this approach is that by processing ranges in sorted order and keeping track of the furthest point reached, we automatically:

1. Merge overlapping ranges (by taking the maximum endpoint)
2. Identify all gaps between ranges
3. Ensure gaps are maximal (we don't split them unnecessarily)

Finally, after processing all ranges, we check if there's a gap at the end of the array (from last+1 to n-1), ensuring we don't miss any uncovered portion at the tail end.

This greedy approach works because once we've processed ranges up to a certain point, we know exactly what's covered and what's not, allowing us to make optimal local decisions that lead to the globally correct answer.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a sweep line approach with greedy processing:

Step 1: Sort the ranges

ranges.sort()

We sort the ranges by their starting positions (Python's default sort for lists). This ensures we process ranges from left to right, making gap detection straightforward.

Step 2: Initialize tracking variables

last = -1
ans = []

• last tracks the rightmost covered position seen so far, initialized to -1 (one position before the array starts)
• ans stores our result list of uncovered ranges

Step 3: Process each range and detect gaps

for l, r in ranges:
    if last + 1 < l:
        ans.append([last + 1, l - 1])
    last = max(last, r)

For each range [l, r]:

• Gap detection: If last + 1 < l, there's a gap between position last + 1 and l - 1. This gap is uncovered, so we add [last + 1, l - 1] to our answer.
• Update coverage: We update last = max(last, r) to handle overlapping ranges. If the current range extends further right than our previous coverage, we extend last. If not (the range is completely contained in already covered area), last remains unchanged.

Step 4: Check for trailing uncovered range

if last + 1 < n:
    ans.append([last + 1, n - 1])

After processing all ranges, if last + 1 < n, there's an uncovered portion at the end of the array from position last + 1 to n - 1.

Why this works:

• By processing ranges in sorted order, we ensure we never miss a gap
• The max(last, r) operation correctly handles overlapping ranges without double-counting
• The gap detection condition last + 1 < l ensures we only add truly uncovered ranges (no adjacent ranges that should be merged)
• Time complexity: O(m log m) where m is the number of ranges (dominated by sorting)
• Space complexity: O(1) extra space (not counting the output array)

Example Walkthrough

Let's trace through a concrete example to see how the algorithm works step by step.

Given:

• n = 12 (array positions 0-11)
• ranges = [[5,7], [2,3], [9,10]]

Step 1: Sort the ranges by start position After sorting: ranges = [[2,3], [5,7], [9,10]]

Step 2: Initialize variables

• last = -1 (tracking rightmost covered position)
• ans = [] (result list)

Step 3: Process each range

Processing range [2,3]:

• Check for gap: last + 1 = 0, range starts at 2
• Since 0 < 2, there's a gap from position 0 to 1
• Add [0, 1] to answer: ans = [[0,1]]
• Update last = max(-1, 3) = 3

Processing range [5,7]:

• Check for gap: last + 1 = 4, range starts at 5
• Since 4 < 5, there's a gap at position 4
• Add [4, 4] to answer: ans = [[0,1], [4,4]]
• Update last = max(3, 7) = 7

Processing range [9,10]:

• Check for gap: last + 1 = 8, range starts at 9
• Since 8 < 9, there's a gap at position 8
• Add [8, 8] to answer: ans = [[0,1], [4,4], [8,8]]
• Update last = max(7, 10) = 10

Step 4: Check for trailing uncovered portion

• last + 1 = 11, n = 12
• Since 11 < 12, there's an uncovered portion at position 11
• Add [11, 11] to answer: ans = [[0,1], [4,4], [8,8], [11,11]]

Final Result: [[0,1], [4,4], [8,8], [11,11]]

This represents the uncovered portions of the array:

• Positions 0-1 are uncovered
• Positions 2-3 are covered by range [2,3]
• Position 4 is uncovered
• Positions 5-7 are covered by range [5,7]
• Position 8 is uncovered
• Positions 9-10 are covered by range [9,10]
• Position 11 is uncovered

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the ranges list.

• The sorting operation takes O(n log n) time
• The subsequent iteration through the sorted ranges takes O(n) time
• Each operation inside the loop (comparison, append, max) takes O(1) time
• Overall time complexity is dominated by the sorting step: O(n log n)

Space Complexity: O(n) in the worst case.

• The sorting operation may use O(log n) to O(n) auxiliary space depending on the implementation (Python's Timsort uses O(n) in worst case)
• The output list ans can contain at most n+1 intervals in the worst case (when no ranges overlap and create maximum gaps)
• Therefore, the total space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Overlapping Ranges Correctly

A critical pitfall occurs when developers forget to use max(last, r) and instead simply set last = r. This breaks when ranges overlap or when a range is completely contained within previously covered area.

Incorrect Code:

for l, r in ranges:
    if last + 1 < l:
        ans.append([last + 1, l - 1])
    last = r  # WRONG! Should be max(last, r)

Problem Example:

• Input: n = 10, ranges = [[1, 5], [2, 3]]
• After processing [1, 5]: last = 5
• After processing [2, 3]: last = 3 (incorrectly moves backward!)
• This would incorrectly report [4, 4] as uncovered when it's actually covered

Solution: Always use last = max(last, r) to ensure we never move the coverage boundary backward.

2. Incorrect Initial Value for last

Setting last = 0 instead of last = -1 causes the algorithm to miss uncovered ranges at the beginning.

Incorrect Code:

last = 0  # WRONG! Should be -1
ans = []

Problem Example:

• Input: n = 5, ranges = [[2, 4]]
• With last = 0, the condition last + 1 < 2 gives 1 < 2, missing position 0
• Would incorrectly output [[1, 1]] instead of [[0, 1]]

Solution: Initialize last = -1 to represent "nothing covered yet" and ensure position 0 can be properly detected as uncovered.

3. Off-by-One Errors in Gap Detection

Developers often make mistakes with the boundary calculations when detecting gaps.

Common Mistakes:

# Mistake 1: Wrong gap boundaries
if last < l:  # Should be last + 1 < l
    ans.append([last, l])  # Should be [last + 1, l - 1]

# Mistake 2: Including already covered positions
if last + 1 <= l:  # Should use < not <=
    ans.append([last + 1, l - 1])

Problem Example:

• Input: n = 10, ranges = [[1, 3], [4, 6]]
• With last + 1 <= l, after processing [1, 3] with last = 3, we'd check 4 <= 4 (true)
• This would add [4, 3] (invalid range) to the answer

Solution: Use strict inequality last + 1 < l and correct boundaries [last + 1, l - 1] for the uncovered range.

4. Forgetting to Check the End of the Array

A common oversight is processing all ranges but forgetting to check if there's an uncovered portion after the last range.

Incomplete Code:

for l, r in ranges:
    if last + 1 < l:
        ans.append([last + 1, l - 1])
    last = max(last, r)
# Missing the final check!
return ans

Problem Example:

• Input: n = 10, ranges = [[0, 5]]
• Without the final check, positions 6-9 would not be reported as uncovered

Solution: Always add the final check after the loop:

if last + 1 < n:
    ans.append([last + 1, n - 1])

5. Not Sorting the Ranges First

Processing ranges in arbitrary order makes gap detection impossible or extremely complex.

Problem Example:

• Input: n = 10, ranges = [[5, 7], [1, 3]]
• Processing [5, 7] first would incorrectly identify [0, 4] as uncovered
• Then processing [1, 3] wouldn't fix the mistake

Solution: Always sort ranges by starting position before processing: ranges.sort()