Find Maximal Uncovered Ranges

You are given an integer n which is the length of a 0-indexed array nums, and a 0-indexed 2D-array ranges, which is a list of sub-ranges of nums (sub-ranges may overlap).

Each row ranges[i] has exactly 2 cells:

ranges[i][0], which shows the start of the ith range (inclusive)

ranges[i][1], which shows the end of the ith range (inclusive)

These ranges cover some cells of nums and leave some cells uncovered. Your task is to find all of the uncovered ranges with maximal length.

Return a 2D-array answer of the uncovered ranges, sorted by the starting point in ascending order.

By all of the uncovered ranges with maximal length, we mean satisfying two conditions:

Each uncovered cell should belong to exactly one sub-range

There should not exist two ranges (l1, r1) and (l2, r2) such that r1 + 1 = l2

class Solution {
    public int[][] findMaximalUncoveredRanges(int n, int[][] ranges) {
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
        int last = -1;
        List<int[]> ans = new ArrayList<>();
        for (int[] range : ranges) {
            int l = range[0], r = range[1];
            if (last + 1 < l) {
                ans.add(new int[] {last + 1, l - 1});
            }
            last = Math.max(last, r);
        }
        if (last + 1 < n) {
            ans.add(new int[] {last + 1, n - 1});
        }
        return ans.toArray(new int[0][]);
    }
}

class Solution:
  def findMaximalUncoveredRanges(self, n: int, ranges: list[list[int]]) -> list[list[int]]:
    ans = []
    start = 0

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

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

    return ans

Range covering problems, like this one, are common in competitive programming and coding interviews because they require careful management of overlapping or adjacent ranges. The general approach is to sort the ranges by their starting points and then process them one by one to identify any gaps. In this problem, the goal is to find all the maximal uncovered ranges, which means identifying sections of the array that are not covered by any given range. Sorting the ranges is a key step, as it allows you to efficiently check where gaps appear and where the ranges overlap.

The solution works by maintaining a pointer, start, to track the beginning of the next uncovered range. As you process each range, if there's a gap between start and the current range, you record that uncovered range. Then, you update start to the end of the current range plus one. The process continues until all ranges are processed, ensuring any leftover uncovered portions of the array are also captured. This approach ensures that each uncovered range is maximally long and doesn't overlap or leave adjacent gaps, a typical goal in range covering problems.

Related Problems