2655. Find Maximal Uncovered Ranges
Problem Description
In this problem, you are given two inputs: an integer n
, specifying the length of a 0-indexed array nums
, and a 2D-array ranges
. Each entry in ranges
represents a sub-range of the array nums
with a start and end index (inclusive). These ranges can overlap each other. The task is to identify and return all the sub-ranges of nums
that are maximally uncovered by any of the ranges provided in ranges
. An uncovered range is considered maximal if:
- Each cell within the uncovered range belongs to just one uncovered sub-range. This implies that uncovered sub-ranges cannot overlap.
- There are no such consecutive uncovered ranges that the end of one is immediately followed by the start of another. Essentially, no two uncovered ranges should be adjacent.
The expected output is a 2D-array of the uncovered ranges, sorted by their start index in ascending order.
Intuition
The intuition behind the solution approach can be broken down into the following steps:
-
Sorting the Ranges: First, we sort the given
ranges
by their start indices. Sorting helps us to process the ranges sequentially, thus making it simpler to find any gaps between successive ranges. -
Finding Uncovered Ranges: We initialize a variable
last
that keeps track of the end index of the last covered sub-range (initialized to -1 since the array is 0-indexed). We then iterate over the sortedranges
, and for each range(l, r)
:a. We check if there is an uncovered range that starts after the end of the last covered range (
last + 1
) and ends before the start of the current range (l - 1
). If such an uncovered range exists, we add it to the answer.b. We update
last
to be the maximum of the current end indexr
and the previously storedlast
, as this keepslast
pointing to the end of the current furthest covered range. -
Checking for Rightmost Uncovered Range: After processing all the given
ranges
, there might still be an uncovered range right at the end of thenums
array. We check if the index one more than the last covered index (last + 1
) is less thann
. If it is, an uncovered sub-range exists fromlast + 1
ton - 1
, and we append this range to our answer. -
Returning the Result: Finally, the 2D-array
ans
contains all the maximally uncovered ranges and is returned as the solution.
Learn more about Sorting patterns.
Solution Approach
The implementation of the solution uses a straightforward approach to solve the problem. Here's a step-by-step explanation:
-
Sort Ranges: The first step is to sort the
ranges
array. This is done with thesort()
method, which sorts the list in place. Sorting is based on the first element of each sub-list, which represents the start of the range. Sorting is critical as it allows us to easily compare the current range with the last uncovered range found.ranges.sort()
-
Initialize Variables: We initialize a list
ans
to collect the answers and a variablelast
to keep track of the end of the last covered range. Thelast
variable starts at-1
since the array is 0-indexed and we want to find if there's an uncovered range starting from the first index (0).last = -1 ans = []
-
Iterate and Find Uncovered Ranges: We loop through each range
(l, r)
in the sortedranges
list. For each range, two main checks occur:a. Uncovered Range Check: If the start of the current range (
l
) is greater thanlast + 1
, there is an uncovered range betweenlast + 1
andl - 1
. This range is added to theans
list.```python if last + 1 < l: ans.append([last + 1, l - 1]) ```
b. Update Last Covered: We then update
last
to be the maximum oflast
and the current range's endr
. This step effectively skips over any overlap and ensures that we extend our covered area to include the current range.```python last = max(last, r) ```
-
Check for Tail Uncovered Range: After the loop, we check if there's an uncovered range from the end of the last covered range to the end of the array
nums
. If such an uncovered range exists, it is added toans
.if last + 1 < n: ans.append([last + 1, n - 1])
-
Return Answer: The
ans
list now contains all the maximal uncovered ranges, sorted by starting point, and can be returned as the final answer.return ans
The simple but effective approach works due to the properties of sorting and the greedy method of extending the covered range to the furthest end reached by any range. The implementation is efficient and straightforward, not requiring any complex algorithms or data structures.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach.
Suppose we are given an integer n = 10
, representing an array nums
of length 10
, and a 2D-array ranges = [[1, 3], [6, 9], [2, 5]]
. We want to find all the maximally uncovered sub-ranges in nums
.
Following the solution approach:
-
Sort Ranges: Sort the
ranges
array to process in order. After sorting based on start index, we get[[1, 3], [2, 5], [6, 9]]
. -
Initialize Variables: We initialize
last = -1
andans = []
. -
Iterate and Find Uncovered Ranges:
- For the first range
[1, 3]
, sincelast + 1
(0) is less than1
, there's an uncovered range[0, 0]
. We add it toans
, resulting inans = [[0, 0]]
. Updatelast
to3
. - For the second range
[2, 5]
,last + 1
(4) is not less than2
, so no new uncovered range is added. Updatelast
to5
(the current end index is not larger thanlast
). - For the third range
[6, 9]
,last + 1
(6) is equal to the start index, so again, no uncovered range is added. Updatelast
to9
.
- For the first range
-
Check for Tail Uncovered Range: After processing all ranges, we check for any uncovered range from the end of the last covered range (
last = 9
) to the length ofnums
(n = 10
). Sincelast + 1
(10) is less thann
, there's an uncovered range[10, 9]
, which is invalid because the start is greater than the end. Thus, no range is added toans
. -
Return Answer: The final answer is
ans = [[0, 0]]
, which is the list of all maximally uncovered ranges innums
.
This example helps us understand how the solution approach works step by step to identify uncovered ranges in the array nums
.
Solution Implementation
1from typing import List # Import List from typing for type annotations
2
3class Solution:
4 def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:
5 # Sort the ranges on the basis of start of each range
6 ranges.sort()
7
8 # Initialize the last seen covered index to -1 (outside the range of indices)
9 last_covered = -1
10 # Initialize a list to store the maximal uncovered ranges
11 uncovered_ranges = []
12
13 # Iterate over the sorted ranges
14 for left, right in ranges:
15 # Check if there's a gap between this range and the last covered index
16 if last_covered + 1 < left:
17 # Append the uncovered range to the list
18 uncovered_ranges.append([last_covered + 1, left - 1])
19
20 # Update the last covered index to be the maximum of current right or the previous last_covered
21 last_covered = max(last_covered, right)
22
23 # After iterating ranges, check if there's still an uncovered range up to n - 1
24 if last_covered + 1 < n:
25 # Append the final uncovered range if any
26 uncovered_ranges.append([last_covered + 1, n - 1])
27
28 # Return the list of uncovered ranges
29 return uncovered_ranges
30
1import java.util.Arrays;
2import java.util.ArrayList;
3import java.util.List;
4
5class Solution {
6
7 /**
8 * Finds the maximal uncovered ranges given a set of ranges and a limit.
9 *
10 * @param n The upper limit (exclusive) for the range of numbers considered.
11 * @param ranges An array of integer arrays, each representing a covered range [start, end].
12 * @return A 2D integer array with the maximal uncovered ranges.
13 */
14 public int[][] findMaximalUncoveredRanges(int n, int[][] ranges) {
15 // Sort the input ranges by the start of each range.
16 Arrays.sort(ranges, (a, b) -> Integer.compare(a[0], b[0]));
17
18 // Initialize the last covered point to -1.
19 int lastCovered = -1;
20
21 // Prepare a list to hold the uncovered ranges.
22 List<int[]> uncoveredRanges = new ArrayList<>();
23
24 // Loop over each range.
25 for (int[] range : ranges) {
26 int start = range[0];
27 int end = range[1];
28
29 // If there is a gap between the last covered point and current range's start,
30 // then it is an uncovered range.
31 if (lastCovered + 1 < start) {
32 uncoveredRanges.add(new int[] {lastCovered + 1, start - 1});
33 }
34
35 // Update the last covered point to the maximum of the current last and range's end.
36 lastCovered = Math.max(lastCovered, end);
37 }
38
39 // After processing all ranges, if there are still uncovered numbers until n,
40 // add the final uncovered range.
41 if (lastCovered + 1 < n) {
42 uncoveredRanges.add(new int[] {lastCovered + 1, n - 1});
43 }
44
45 // Convert the list of uncovered ranges to a 2D array and return.
46 return uncoveredRanges.toArray(new int[uncoveredRanges.size()][]);
47 }
48}
49
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Finds maximal uncovered ranges given an upper bound 'n' and a list of ranges
7 vector<vector<int>> findMaximalUncoveredRanges(int n, vector<vector<int>>& ranges) {
8 // Sort the ranges based on their start points
9 sort(ranges.begin(), ranges.end(), [](const vector<int>& firstRange, const vector<int>& secondRange) {
10 return firstRange[0] < secondRange[0];
11 });
12
13 int lastCovered = -1;
14 vector<vector<int>> uncoveredRanges;
15
16 // Iterate through each range
17 for (auto& range : ranges) {
18 int start = range[0], end = range[1];
19
20 // Check if there is an uncovered range before the start of the current range
21 if (lastCovered + 1 < start) {
22 // Add the uncovered range to the answer list
23 uncoveredRanges.push_back({lastCovered + 1, start - 1});
24 }
25 // Update the last covered position with the furthest point covered so far
26 lastCovered = max(lastCovered, end);
27 }
28
29 // After all ranges are processed, check if there's an uncovered range at the end
30 if (lastCovered + 1 < n) {
31 // Add the uncovered range up to 'n - 1' to the answer list
32 uncoveredRanges.push_back({lastCovered + 1, n - 1});
33 }
34
35 return uncoveredRanges;
36 }
37};
38
1function findMaximalUncoveredRanges(n: number, ranges: number[][]): number[][] {
2 // Sort the given ranges based on their starting points.
3 ranges.sort((firstRange, secondRange) => {
4 return firstRange[0] - secondRange[0];
5 });
6
7 let lastCovered: number = -1;
8 let uncoveredRanges: number[][] = [];
9
10 // Iterate through the sorted ranges.
11 ranges.forEach((range) => {
12 const [start, end] = range;
13
14 // Check for an uncovered range before the start of the current range.
15 if (lastCovered + 1 < start) {
16 // Add the uncovered range to the uncoveredRanges array.
17 uncoveredRanges.push([lastCovered + 1, start - 1]);
18 }
19
20 // Update the lastCovered marker with the maximum of lastCovered and current end point.
21 lastCovered = Math.max(lastCovered, end);
22 });
23
24 // After processing all ranges, check for an uncovered range at the end.
25 if (lastCovered + 1 < n) {
26 // Add the final uncovered range up to 'n - 1' to the uncoveredRanges array.
27 uncoveredRanges.push([lastCovered + 1, n - 1]);
28 }
29
30 // Return the array containing all the uncovered ranges.
31 return uncoveredRanges;
32}
33
Time and Space Complexity
The time complexity of the provided code primarily depends on the sorting of the ranges and the subsequent iteration through the sorted ranges list.
-
Sorting the ranges: The sort operation for the ranges at the beginning of the function has a time complexity of
O(m log m)
, wherem
is the number of intervals in the ranges list. -
Iterating through the sorted ranges: The iteration through ranges involves comparing and possibly appending to the
ans
list. This iteration occurs once for each element in the ranges list, giving it a time complexity ofO(m)
. -
Combining the above steps: Since the sort operation dominates the overall time complexity, we can state that the overall time complexity of the function is
O(m log m)
.
The space complexity of the code comes from the additional memory used to store the ans
list.
- Space for
ans
list: In the worst case, theans
list could potentially store every single uncovered range between adjacent ranges in the sorted list as well as the uncovered range before the first range and after the last range if applicable. This worst-case scenario happens when none of the ranges overlap at all, which theoretically could create up tom+1
entries in theans
list in the case where each interval has a gap with adjacent intervals. Thus, the space complexity isO(m)
.
In summary:
- The Time Complexity of the code is
O(m log m)
. - The Space Complexity of the code is
O(m)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!