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:
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]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.
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.
| 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 |
Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 331,616 views views
Watch 9 more video solutions →Practice Find Maximal Uncovered Ranges with our built-in code editor and test cases.
Practice on FleetCode