Find Maximal Uncovered Ranges solution and explanation
The 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-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
Example 1:
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:
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:
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 <= 1090 <= ranges.length <= 106ranges[i].length = 20 <= ranges[i][j] <= n - 1ranges[i][0] <= ranges[i][1]
Approach overview
Problem Overview: You get an integer n representing the range [0, n-1] and a list of covered intervals. The task is to return all maximal contiguous ranges that are not covered by any interval.
Approach 1: Brute Force Marking (O(n + m * k) time, O(n) space)
Create a boolean array of size n where each index represents whether that position is covered. Iterate through every interval and mark the corresponding indices as covered. After marking, scan the array to collect maximal contiguous segments where coverage is false. This approach is straightforward but inefficient when n is large because every element inside each interval may be visited.
Approach 2: Sorting and Gap Detection (O(m log m) time, O(1) extra space)
Sort the intervals by their starting point using a standard sorting technique. Track the end of the last covered position while iterating through the sorted intervals. Whenever the next interval starts after the current covered boundary, the gap between them forms an uncovered range. Update the current boundary with max(currentEnd, intervalEnd) to handle overlaps and merged coverage. This approach works well because sorted intervals allow you to detect gaps with a single linear scan.
After processing all intervals, check if the last covered boundary is less than n - 1. If so, the remaining segment forms the final uncovered range. The logic resembles interval merging problems commonly seen with array processing and sorting patterns.
Recommended for interviews: The sorting + gap detection approach. Interviewers expect you to recognize this as an interval problem: sort the intervals, track the current merged coverage, and output gaps. Brute force demonstrates the basic idea of coverage, but the sorted scan shows you understand interval merging and optimal time complexity.
Solution
We sort all intervals by their left endpoints in ascending order, then traverse all intervals from left to right, maintaining a variable last to represent the rightmost endpoint that has been covered so far, initially last=-1.
If the left endpoint of the current interval is greater than last+1, it means [last+1, l-1] is an uncovered interval, and we add it to the answer array. Then we update last to the right endpoint of the current interval and continue traversing the next interval. After traversing all intervals, if last+1 < n, it means [last+1, n-1] is an uncovered interval, and we add it to the answer array.
Finally, we return the answer array.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array ranges.
class Solution:
def findMaximalUncoveredRanges(
self, n: int, ranges: List[List[int]]
) -> List[List[int]]:
ranges.sort()
last = -1
ans = []
for l, r in ranges:
if last + 1 < l:
ans.append([last + 1, l - 1])
last = max(last, r)
if last + 1 < n:
ans.append([last + 1, n - 1])
return ansclass 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 {
public:
vector<vector<int>> findMaximalUncoveredRanges(int n, vector<vector<int>>& ranges) {
sort(ranges.begin(), ranges.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
int last = -1;
vector<vector<int>> ans;
for (auto& range : ranges) {
int l = range[0], r = range[1];
if (last + 1 < l) {
ans.push_back({last + 1, l - 1});
}
last = max(last, r);
}
if (last + 1 < n) {
ans.push_back({last + 1, n - 1});
}
return ans;
}
};function findMaximalUncoveredRanges(n: number, ranges: number[][]): number[][] {
ranges.sort((a, b) => a[0] - b[0]);
let last = -1;
const ans: number[][] = [];
for (const [l, r] of ranges) {
if (last + 1 < l) {
ans.push([last + 1, l - 1]);
}
last = Math.max(last, r);
}
if (last + 1 < n) {
ans.push([last + 1, n - 1]);
}
return ans;
}func findMaximalUncoveredRanges(n int, ranges [][]int) (ans [][]int) {
sort.Slice(ranges, func(i, j int) bool { return ranges[i][0] < ranges[j][0] })
last := -1
for _, r := range ranges {
if last+1 < r[0] {
ans = append(ans, []int{last + 1, r[0] - 1})
}
last = max(last, r[1])
}
if last+1 < n {
ans = append(ans, []int{last + 1, n - 1})
}
return
}impl Solution {
pub fn find_maximal_uncovered_ranges(n: i32, mut ranges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
ranges.sort_by_key(|x| x[0]);
let mut last = -1;
let mut ans = Vec::new();
for range in ranges {
let l = range[0];
let r = range[1];
if last + 1 < l {
ans.push(vec![last + 1, l - 1]);
}
last = last.max(r);
}
if last + 1 < n {
ans.push(vec![last + 1, n - 1]);
}
ans
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Marking | O(n + m * k) | O(n) | Small n where marking coverage directly is simple and acceptable |
| Sorting + Gap Detection | O(m log m) | O(1) | General case with many intervals; standard optimal interview approach |
Frequently asked questions
Is Find Maximal Uncovered Ranges easy or hard?
Find Maximal Uncovered Ranges is considered a Medium-level problem. The challenge is recognizing it as an interval merging and gap detection problem, which requires sorting and careful boundary updates.
Find Maximal Uncovered Ranges Python/Java solution
Most implementations sort the intervals, track the current covered boundary, and append gaps to a result list. The same logic translates cleanly to Python, Java, C++, Go, TypeScript, and Rust because it relies only on sorting and a linear pass.
How to solve Find Maximal Uncovered Ranges in O(n)?
True O(n) is possible only if the range size n is small and you use a coverage array. Mark each interval as covered in a boolean array and scan for uncovered segments. This uses O(n) space and O(n + total interval length) time, which is practical only when n is manageable.
What is the best approach for Find Maximal Uncovered Ranges?
The most efficient approach sorts the intervals by start position and scans them to detect gaps. While iterating, maintain the farthest covered endpoint and output any gap before the next interval begins. This sorting-based interval scan runs in O(m log m) time and O(1) extra space.
Is Find Maximal Uncovered Ranges asked at Google/Amazon/Meta?
Interval and gap-detection problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem ID may vary, the pattern of sorting intervals and finding uncovered gaps is a common interview topic.
What data structure is used in Find Maximal Uncovered Ranges?
The solution primarily uses arrays to store intervals and relies on sorting. During the scan, only a few variables track the current merged boundary and detected gaps, so no advanced data structures are required.
What is the time complexity of Find Maximal Uncovered Ranges?
The optimal solution runs in O(m log m) time due to sorting the intervals, followed by a linear scan. The scan itself is O(m). Space complexity is O(1) if the intervals are processed in-place, excluding the output list.