Problem

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-arrayanswer 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

Examples

Example 1:

1
2
3

Input: n = 10, ranges = [[3,5],[7,8]]
Output: [[0,2],[6,6],[9,9]]
Explanation: The ranges (3, 5) and (7, 8) are covered, so if we simplify the array nums to a binary array where 0 shows an uncovered cell and 1 shows a covered cell, the array becomes [0,0,0,1,1,1,0,1,1,0] in which we can observe that the ranges (0, 2), (6, 6) and (9, 9) aren't covered.

Example 2:

1
2
3

Input: n = 3, ranges = [[0,2]]
Output: []
Explanation: In this example, the whole of the array nums is covered and there are no uncovered cells so the output is an empty array.

Example 3:

1
2
3

Input: n = 7, ranges = [[2,4],[0,3]]
Output: [[5,6]]
Explanation: The ranges (0, 3) and (2, 4) are covered, so if we simplify the array nums to a binary array where 0 shows an uncovered cell and 1 shows a covered cell, the array becomes [1,1,1,1,1,0,0] in which we can observe that the range (5, 6) is uncovered.

Constraints:

  • 1 <= n <= 10^9
  • 0 <= ranges.length <= 10^6
  • ranges[i].length = 2
  • 0 <= ranges[i][j] <= n - 1
  • ranges[i][0] <= ranges[i][1]

Solution

Method 1 – Merge Intervals and Find Gaps

Intuition

To find maximal uncovered ranges, we first merge all overlapping and adjacent covered ranges, then identify the gaps between them. Each gap is a maximal uncovered range.

Approach

  1. Sort the input ranges by their start value.
  2. Merge overlapping and adjacent ranges into a list of non-overlapping intervals.
  3. Initialize a pointer at 0 and iterate through the merged intervals:
    • For each interval, if the pointer is less than the interval’s start, add [pointer, interval.start-1] as an uncovered range.
    • Move the pointer to interval.end+1.
  4. After processing all intervals, if the pointer is less than n, add [pointer, n-1] as the last uncovered range.
  5. Return all uncovered ranges found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> findMaximalUncoveredRanges(int n, vector<vector<int>>& ranges) {
        sort(ranges.begin(), ranges.end());
        vector<vector<int>> merged;
        for (auto& r : ranges) {
            if (merged.empty() || merged.back()[1] < r[0] - 1) merged.push_back(r);
            else merged.back()[1] = max(merged.back()[1], r[1]);
        }
        vector<vector<int>> ans;
        int prev = 0;
        for (auto& r : merged) {
            if (prev < r[0]) ans.push_back({prev, r[0]-1});
            prev = r[1]+1;
        }
        if (prev < n) ans.push_back({prev, n-1});
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func findMaximalUncoveredRanges(n int, ranges [][]int) [][]int {
    sort.Slice(ranges, func(i, j int) bool { return ranges[i][0] < ranges[j][0] })
    merged := [][]int{}
    for _, r := range ranges {
        if len(merged) == 0 || merged[len(merged)-1][1] < r[0]-1 {
            merged = append(merged, r)
        } else {
            merged[len(merged)-1][1] = max(merged[len(merged)-1][1], r[1])
        }
    }
    ans := [][]int{}
    prev := 0
    for _, r := range merged {
        if prev < r[0] {
            ans = append(ans, []int{prev, r[0]-1})
        }
        prev = r[1]+1
    }
    if prev < n {
        ans = append(ans, []int{prev, n-1})
    }
    return ans
}
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public List<List<Integer>> findMaximalUncoveredRanges(int n, int[][] ranges) {
        Arrays.sort(ranges, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] r : ranges) {
            if (merged.isEmpty() || merged.get(merged.size()-1)[1] < r[0]-1) merged.add(r);
            else merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], r[1]);
        }
        List<List<Integer>> ans = new ArrayList<>();
        int prev = 0;
        for (int[] r : merged) {
            if (prev < r[0]) ans.add(Arrays.asList(prev, r[0]-1));
            prev = r[1]+1;
        }
        if (prev < n) ans.add(Arrays.asList(prev, n-1));
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun findMaximalUncoveredRanges(n: Int, ranges: Array<IntArray>): List<List<Int>> {
        ranges.sortBy { it[0] }
        val merged = mutableListOf<IntArray>()
        for (r in ranges) {
            if (merged.isEmpty() || merged.last()[1] < r[0]-1) merged.add(r)
            else merged.last()[1] = maxOf(merged.last()[1], r[1])
        }
        val ans = mutableListOf<List<Int>>()
        var prev = 0
        for (r in merged) {
            if (prev < r[0]) ans.add(listOf(prev, r[0]-1))
            prev = r[1]+1
        }
        if (prev < n) ans.add(listOf(prev, n-1))
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findMaximalUncoveredRanges(self, n: int, ranges: list[list[int]]) -> list[list[int]]:
        ranges.sort()
        merged = []
        for r in ranges:
            if not merged or merged[-1][1] < r[0]-1:
                merged.append(r[:])
            else:
                merged[-1][1] = max(merged[-1][1], r[1])
        ans = []
        prev = 0
        for r in merged:
            if prev < r[0]:
                ans.append([prev, r[0]-1])
            prev = r[1]+1
        if prev < n:
            ans.append([prev, n-1])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn find_maximal_uncovered_ranges(n: i32, mut ranges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        ranges.sort();
        let mut merged = vec![];
        for r in ranges {
            if merged.is_empty() || merged.last().unwrap()[1] < r[0]-1 {
                merged.push(r);
            } else {
                let last = merged.last_mut().unwrap();
                last[1] = last[1].max(r[1]);
            }
        }
        let mut ans = vec![];
        let mut prev = 0;
        for r in &merged {
            if prev < r[0] {
                ans.push(vec![prev, r[0]-1]);
            }
            prev = r[1]+1;
        }
        if prev < n {
            ans.push(vec![prev, n-1]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    findMaximalUncoveredRanges(n: number, ranges: number[][]): number[][] {
        ranges.sort((a, b) => a[0] - b[0]);
        const merged: number[][] = [];
        for (const r of ranges) {
            if (!merged.length || merged[merged.length-1][1] < r[0]-1) merged.push([...r]);
            else merged[merged.length-1][1] = Math.max(merged[merged.length-1][1], r[1]);
        }
        const ans: number[][] = [];
        let prev = 0;
        for (const r of merged) {
            if (prev < r[0]) ans.push([prev, r[0]-1]);
            prev = r[1]+1;
        }
        if (prev < n) ans.push([prev, n-1]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k log k + n), where k is the number of input ranges. Sorting and merging is O(k log k), and finding gaps is O(k).
  • 🧺 Space complexity: O(k), for storing merged intervals and output.