LeetCode 2655 - Find Maximal Uncovered Ranges

The problem gives us an integer n, representing a conceptual array nums of length n, indexed from 0 to n - 1. We are also given a list of inclusive ranges, where each range marks positions in the array as covered.

leetcodemediumarraysorting

LeetCode Problem 2655

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

LeetCode 2655 - Find Maximal Uncovered Ranges

Problem Understanding

The problem gives us an integer n, representing a conceptual array nums of length n, indexed from 0 to n - 1. We are also given a list of inclusive ranges, where each range marks positions in the array as covered.

Our task is to determine every maximal uncovered segment of the array.

An uncovered range is a contiguous block of indices that are not included in any of the given covered ranges. The term maximal is important here. It means that if two uncovered intervals are adjacent, they must be merged into a single larger uncovered interval. In other words, the final answer should contain the largest possible contiguous uncovered segments.

For example, if n = 10 and the covered ranges are [3,5] and [7,8], then the covered indices are:

  • 3,4,5
  • 7,8

The uncovered indices are:

  • 0,1,2
  • 6
  • 9

Since these uncovered groups are separated by covered cells, they remain separate maximal uncovered ranges:

[[0,2],[6,6],[9,9]]

The constraints are very important:

  • n can be as large as 10^9
  • ranges.length can be as large as 10^6

These limits immediately tell us that we cannot explicitly build the entire array. Any solution that tries to create a boolean array of size n would be infeasible in both time and memory.

Instead, the solution must operate directly on the intervals themselves.

There are several important edge cases to recognize early:

  • The ranges may overlap heavily.
  • The ranges may already cover the entire array.
  • The ranges list may be empty, meaning the entire array is uncovered.
  • Adjacent covered intervals should effectively behave like one merged interval because they leave no uncovered space between them.
  • The uncovered interval may appear before the first covered range or after the last covered range.

The problem guarantees that all ranges are valid and within bounds, so we do not need additional validation logic.

Approaches

Brute Force Approach

A straightforward solution would be to simulate the entire array.

We could create a boolean array of length n, initially marking every position as uncovered. Then, for every range [l, r], we mark all indices from l through r as covered.

After processing all ranges, we scan the array to collect maximal contiguous uncovered segments.

This works correctly because every position is explicitly tracked. However, the complexity is unacceptable for the given constraints.

Since n can be up to 10^9, constructing such an array is impossible in practice.

Optimal Approach

The key observation is that we never actually need to represent individual cells unless they are boundaries of intervals.

Instead, we can:

  1. Sort all ranges by starting position.
  2. Merge overlapping or adjacent covered ranges.
  3. Track the gaps between merged covered intervals.

Those gaps are exactly the maximal uncovered ranges.

For example:

ranges = [[2,4],[0,3]]

After sorting:

[[0,3],[2,4]]

After merging:

[[0,4]]

Now we can easily see that the uncovered portion is:

[5,6]

This interval-based approach is efficient because it processes only the given ranges rather than the entire conceptual array.

Approach Time Complexity Space Complexity Notes
Brute Force O(n + total covered cells) O(n) Explicitly marks every array position
Optimal O(m log m) O(m) Sorts and merges intervals, where m is the number of ranges

Here, m = ranges.length.

Algorithm Walkthrough

  1. First, sort the ranges by their starting coordinate.

Sorting allows us to process intervals from left to right and efficiently merge overlaps. 2. Initialize an empty result list to store uncovered ranges. 3. Maintain a variable called current_end.

This variable represents the furthest covered position processed so far.

Initially:

current_end = -1

This means nothing has been covered yet. 4. Iterate through the sorted ranges one by one.

For each interval [start, end], compare it against current_end. 5. If start > current_end + 1, then there is a gap between the previous covered region and the current interval.

The uncovered interval is:

[current_end + 1, start - 1]

Add this interval to the answer. 6. Update current_end.

Since intervals may overlap, we extend the covered region using:

current_end = max(current_end, end)
  1. After processing all ranges, there may still be an uncovered suffix at the end of the array.

If:

current_end < n - 1

then the remaining uncovered interval is:

[current_end + 1, n - 1]
  1. Return the collected uncovered intervals.

Why it works

The algorithm maintains the invariant that current_end always represents the furthest covered index among all processed intervals.

Because the ranges are processed in sorted order, any gap between current_end and the next interval's start must represent a maximal uncovered segment.

Merging overlaps ensures that no covered region is counted twice and no artificial gaps are introduced.

Therefore, every uncovered interval is found exactly once, and all returned intervals are maximal.

Python Solution

from typing import List

class Solution:
    def findMaximalUncoveredRanges(
        self,
        n: int,
        ranges: List[List[int]]
    ) -> List[List[int]]:
        
        if not ranges:
            return [[0, n - 1]]

        ranges.sort()

        uncovered = []
        current_end = -1

        for start, end in ranges:

            if start > current_end + 1:
                uncovered.append([current_end + 1, start - 1])

            current_end = max(current_end, end)

        if current_end < n - 1:
            uncovered.append([current_end + 1, n - 1])

        return uncovered

The implementation begins by handling the simplest edge case. If there are no covered ranges, then the entire array is uncovered, so we immediately return [0, n - 1].

Next, the ranges are sorted. Python's default list sorting naturally sorts by the first element and then the second element, which is exactly what we need.

The variable current_end tracks the furthest covered position encountered so far.

During iteration, if the next interval starts strictly after current_end + 1, then there is a genuine uncovered gap. That gap is appended to the answer list.

Afterward, we update current_end using the maximum value to merge overlapping intervals naturally.

Finally, after processing all ranges, we check whether any uncovered suffix remains at the end of the array.

Go Solution

package main

import "sort"

func findMaximalUncoveredRanges(n int, ranges [][]int) [][]int {

	if len(ranges) == 0 {
		return [][]int{{0, n - 1}}
	}

	sort.Slice(ranges, func(i, j int) bool {
		if ranges[i][0] == ranges[j][0] {
			return ranges[i][1] < ranges[j][1]
		}
		return ranges[i][0] < ranges[j][0]
	})

	result := [][]int{}
	currentEnd := -1

	for _, interval := range ranges {
		start := interval[0]
		end := interval[1]

		if start > currentEnd+1 {
			result = append(result, []int{currentEnd + 1, start - 1})
		}

		if end > currentEnd {
			currentEnd = end
		}
	}

	if currentEnd < n-1 {
		result = append(result, []int{currentEnd + 1, n - 1})
	}

	return result
}

The Go implementation follows the same logic as the Python solution.

The main difference is that Go requires explicit sorting logic using sort.Slice. We also explicitly manage slice appends when building the result.

There are no integer overflow concerns because the constraints fit safely within Go's standard integer range.

Go slices naturally handle dynamic growth for the result intervals.

Worked Examples

Example 1

Input:

n = 10
ranges = [[3,5],[7,8]]

Step 1: Sort ranges

[[3,5],[7,8]]

Already sorted.

Step 2: Initialize variables

Variable Value
current_end -1
uncovered []

Step 3: Process interval [3,5]

Check:

3 > -1 + 1
3 > 0

True, so uncovered range:

[0,2]

Update state:

Variable Value
uncovered [[0,2]]
current_end 5

Step 4: Process interval [7,8]

Check:

7 > 5 + 1
7 > 6

True, so uncovered range:

[6,6]

Update state:

Variable Value
uncovered [[0,2],[6,6]]
current_end 8

Step 5: Final suffix check

8 < 9

True, so append:

[9,9]

Final answer:

[[0,2],[6,6],[9,9]]

Example 2

Input:

n = 3
ranges = [[0,2]]

Process interval

Variable Value
current_end 2
uncovered []

Final suffix check:

2 < 2

False.

Final answer:

[]

Example 3

Input:

n = 7
ranges = [[2,4],[0,3]]

Step 1: Sort ranges

[[0,3],[2,4]]

Step 2: Process [0,3]

No gap exists because:

0 > 0

False.

Update:

Variable Value
current_end 3

Step 3: Process [2,4]

Check:

2 > 4

False.

Merge overlap:

Variable Value
current_end 4

Step 4: Final suffix

4 < 6

True.

Append:

[5,6]

Final answer:

[[5,6]]

Complexity Analysis

Measure Complexity Explanation
Time O(m log m) Sorting the ranges dominates the runtime
Space O(m) Output storage and sorting overhead

The algorithm processes each interval exactly once after sorting. The sorting step is the dominant cost.

No auxiliary structure proportional to n is created, which is crucial because n may be extremely large.

Test Cases

from typing import List

class Solution:
    def findMaximalUncoveredRanges(
        self,
        n: int,
        ranges: List[List[int]]
    ) -> List[List[int]]:
        
        if not ranges:
            return [[0, n - 1]]

        ranges.sort()

        uncovered = []
        current_end = -1

        for start, end in ranges:

            if start > current_end + 1:
                uncovered.append([current_end + 1, start - 1])

            current_end = max(current_end, end)

        if current_end < n - 1:
            uncovered.append([current_end + 1, n - 1])

        return uncovered

sol = Solution()

assert sol.findMaximalUncoveredRanges(
    10,
    [[3,5],[7,8]]
) == [[0,2],[6,6],[9,9]]  # provided example

assert sol.findMaximalUncoveredRanges(
    3,
    [[0,2]]
) == []  # entire array covered

assert sol.findMaximalUncoveredRanges(
    7,
    [[2,4],[0,3]]
) == [[5,6]]  # overlapping ranges

assert sol.findMaximalUncoveredRanges(
    5,
    []
) == [[0,4]]  # no ranges at all

assert sol.findMaximalUncoveredRanges(
    8,
    [[1,2],[4,5]]
) == [[0,0],[3,3],[6,7]]  # multiple separate gaps

assert sol.findMaximalUncoveredRanges(
    6,
    [[0,1],[2,3],[4,5]]
) == []  # adjacent intervals cover everything

assert sol.findMaximalUncoveredRanges(
    10,
    [[1,7]]
) == [[0,0],[8,9]]  # uncovered prefix and suffix

assert sol.findMaximalUncoveredRanges(
    10,
    [[1,3],[2,5],[4,8]]
) == [[0,0],[9,9]]  # chained overlap merging

assert sol.findMaximalUncoveredRanges(
    1,
    []
) == [[0,0]]  # smallest possible n

assert sol.findMaximalUncoveredRanges(
    1,
    [[0,0]]
) == []  # smallest fully covered array
Test Why
[[3,5],[7,8]] Validates standard gap detection
[[0,2]] Ensures fully covered arrays return empty
[[2,4],[0,3]] Validates overlap merging
[] Ensures entire array is uncovered
[[1,2],[4,5]] Tests multiple uncovered gaps
[[0,1],[2,3],[4,5]] Tests adjacent intervals with no gaps
[[1,7]] Tests uncovered prefix and suffix
[[1,3],[2,5],[4,8]] Tests chained interval merging
n = 1, [] Smallest boundary case
n = 1, [[0,0]] Smallest fully covered case

Edge Cases

One important edge case occurs when the ranges list is empty. In this scenario, no positions are covered, so the entire array from 0 to n - 1 must be returned as a single maximal uncovered interval. A naive implementation might accidentally return an empty list because it never enters the processing loop. The implementation handles this explicitly at the beginning.

Another important case involves overlapping intervals such as [[1,4],[2,6]]. If overlaps are not merged correctly, the algorithm could incorrectly identify fake uncovered gaps between intervals. The solution avoids this by maintaining current_end as the furthest covered position seen so far.

Adjacent intervals are another subtle case. For example:

[[0,2],[3,5]]

Although these intervals do not overlap, they leave no uncovered cells between them. A buggy implementation might incorrectly create an uncovered interval between 2 and 3. The condition:

start > current_end + 1

correctly prevents this issue because adjacency does not produce a gap.

Finally, uncovered regions at the beginning or end of the array can easily be missed. The implementation handles the beginning naturally through the initial value current_end = -1, and handles the suffix through the final post-processing check after all intervals are processed.