Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python
Find Maximal Uncovered Ranges - Video Solution
Watch 10 video solutions for Find Maximal Uncovered Ranges, a medium level problem involving Array, Sorting. This walkthrough by NeetCode has 331,616 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
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 |