Check if All the Integers in a Range Are Covered
EasyPrompt
You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [starti, endi] represents an inclusive interval between starti and endi.
Return true if each integer in the inclusive range [left, right] is covered by at least one interval in ranges. Return false otherwise.
An integer x is covered by an interval ranges[i] = [starti, endi] if starti <= x <= endi.
Example 1:
Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
Output: true
Explanation: Every integer between 2 and 5 is covered:
- 2 is covered by the first range.
- 3 and 4 are covered by the second range.
- 5 is covered by the third range.Example 2:
Input: ranges = [[1,10],[10,20]], left = 21, right = 21
Output: false
Explanation: 21 is not covered by any range.
Constraints:
1 <= ranges.length <= 501 <= starti <= endi <= 501 <= left <= right <= 50
Approaches
4 approaches with complexity analysis and trade-offs.
The most straightforward approach is to simulate the process directly. We can check each integer in the required range [left, right] one by one. For each integer, we scan through the entire ranges array to see if any interval covers it. If we find an integer that is not covered by any of the intervals, we can stop and return false. If we successfully verify that all integers from left to right are covered, we return true.
Algorithm
- Iterate through each integer
ifromlefttoright. - For each integer
i, assume it's not covered by setting a flagisCovered = false. - Iterate through every interval
[start, end]in therangesarray. - If
ifalls within the current interval (i.e.,start <= i <= end), setisCovered = trueand break the inner loop, as we've found a cover fori. - After checking all ranges, if the
isCoveredflag is stillfalse, it means the integeriis not covered by any interval. In this case, we can immediately conclude that not all integers are covered, so we returnfalse. - If the outer loop completes without returning
false, it means every integer fromlefttorightwas successfully found in at least one interval. Returntrue.
Walkthrough
This method involves a nested loop structure. The outer loop iterates through each integer i from left to right. The inner loop iterates through each interval in the ranges array. Inside the inner loop, we check if the current integer i is within the bounds of the current interval. If it is, we know this number is covered and can move on to the next integer in the outer loop. If the inner loop completes without finding a covering interval for i, we have found a number in the [left, right] range that is not covered, and we can immediately return false.
class Solution { public boolean isCovered(int[][] ranges, int left, int right) { // Iterate over each integer from left to right. for (int i = left; i <= right; i++) { boolean isNumCovered = false; // Check if the integer 'i' is covered by any of the ranges. for (int[] range : ranges) { if (i >= range[0] && i <= range[1]) { isNumCovered = true; break; // Found a cover, move to the next integer. } } // If after checking all ranges, 'i' is not covered, return false. if (!isNumCovered) { return false; } } // If all integers from left to right are covered, return true. return true; }}Complexity
Time
O((right - left + 1) * N), where N is the number of intervals in `ranges`. For each of the `right - left + 1` integers, we may have to scan all N intervals.
Space
O(1), as we only use a few variables to keep track of the current state.
Trade-offs
Pros
Very simple to understand and implement.
Requires no extra space, i.e., O(1) space complexity.
Cons
This approach is inefficient if the range
[left, right]is large or if the number of intervals is large, as it re-scans therangesarray for each number in the target range.
Given the small constraints on the values (1 to 50), we can use an auxiliary array to keep track of which numbers are covered. We can create a boolean array representing the number line up to 50. We first pass through all the given ranges and mark every number they cover as true in our boolean array. After this pre-processing step, we just need to check our target range [left, right] against this array. If any number from left to right is marked false, we return false.
Algorithm
- Create a boolean array,
covered, of size 52 (to handle numbers up to 50), and initialize all its elements tofalse. - Iterate through each interval
[start, end]in therangesarray. - For each interval, run a loop from
starttoend. In this loop, mark every integerjas covered by settingcovered[j] = true. - After populating the
coveredarray, iterate through the target range fromlefttoright. - For each integer
iin this range, check ifcovered[i]istrue. - If
covered[i]isfalsefor anyi, it means that number is not covered. Returnfalse. - If the loop completes, it means all numbers in the range
[left, right]are covered. Returntrue.
Walkthrough
This approach uses a boolean array, say covered, to act as a map for all possible numbers in the problem's scope. The size of this array will be 52 to accommodate indices from 1 to 51. We first iterate through all the intervals provided in ranges. For each interval [start, end], we iterate from start to end and set covered[i] = true for each i. This effectively marks all numbers that are covered by at least one interval. Once this marking phase is complete, we perform a second pass, this time only over our target range from left to right. We check covered[i] for each i in this range. If we encounter a false value, we know that number is not covered, and we return false. If we get through the entire [left, right] range without finding any uncovered numbers, we return true.
class Solution { public boolean isCovered(int[][] ranges, int left, int right) { boolean[] covered = new boolean[52]; // Indices 1 to 51 // Mark all numbers covered by the ranges. for (int[] range : ranges) { for (int i = range[0]; i <= range[1]; i++) { if (i < covered.length) { // Boundary check covered[i] = true; } } } // Check if all numbers in the [left, right] range are marked as covered. for (int i = left; i <= right; i++) { if (!covered[i]) { return false; } } return true; }}Complexity
Time
O(N * L + (right - left)), where N is the number of ranges and L is the average length of a range. In the worst case, this is O(N*K) where K is the max coordinate value.
Space
O(K), where K is the maximum possible value of a coordinate (51 in this case).
Trade-offs
Pros
Conceptually simple and avoids nested loops during the check phase.
Efficient when the range of numbers is small and fixed.
Cons
The space complexity depends on the maximum possible value of the coordinates, which could be large in other problems.
The time complexity is dependent on the size of the intervals, which can lead to many redundant write operations if intervals overlap significantly.
A more efficient approach for interval problems is to first sort the intervals and then process them in a greedy manner. By sorting the intervals by their start points, we can iterate through them once and extend our covered region as far as possible. This avoids redundant checks and doesn't depend on the size of the [left, right] range, only on the number of intervals.
Algorithm
- Sort the
rangesarray based on the start time of each interval. If start times are equal, sorting by end time is not strictly necessary but is good practice. - Initialize a variable
covered_reachtoleft - 1. This variable will track the maximum integer we have covered so far, starting from the beginning of our target range. - Iterate through the sorted
ranges. - For each
range = [start, end]:- If the
startof the current range is greater thancovered_reach + 1, it means there is a gap between what we have covered and the start of the next available interval. We cannot cover this gap, so we can stop and conclude the range is not fully covered. - If
start <= covered_reach + 1, it means this interval is adjacent to or overlaps with our currently covered region. We can use it to extend our coverage. Updatecovered_reach = max(covered_reach, end). - After updating
covered_reach, check ifcovered_reach >= right. If it is, we have successfully covered the entire target range, and we can returntrue.
- If the
- If the loop finishes, we make one final check:
return covered_reach >= right.
Walkthrough
This method first sorts the ranges array by the starting points of the intervals. Then, it greedily tries to cover the range [left, right]. We use a variable, covered_reach, to keep track of the farthest point reached starting from left. We initialize covered_reach to left - 1. We then iterate through the sorted intervals. For each interval, we check if it can help extend our covered_reach. An interval [start, end] can help if it starts at or before covered_reach + 1. If it does, we update covered_reach to the maximum of its current value and the interval's end. If at any point we find an interval that starts after covered_reach + 1, we know there's a gap that cannot be bridged. If our covered_reach becomes greater than or equal to right, we have succeeded. This approach effectively merges intervals on the fly without needing to store a separate merged list.
import java.util.Arrays; class Solution { public boolean isCovered(int[][] ranges, int left, int right) { Arrays.sort(ranges, (a, b) -> Integer.compare(a[0], b[0])); int covered_reach = left - 1; for (int[] range : ranges) { int start = range[0]; int end = range[1]; // If the current range starts after the point we need to cover next, // there's a gap. However, we can just continue checking other ranges // that might start earlier but appear later due to sorting order. // The key is to extend the reach if possible. if (start <= covered_reach + 1) { covered_reach = Math.max(covered_reach, end); } // If we have covered the entire target range, we can stop early. if (covered_reach >= right) { return true; } } return covered_reach >= right; }}Complexity
Time
O(N log N), where N is the number of intervals. The sorting takes O(N log N) and the subsequent pass takes O(N).
Space
O(log N) or O(N), depending on the space used by the sorting algorithm.
Trade-offs
Pros
Efficient, with a time complexity dominated by sorting.
Independent of the length of the
[left, right]range, making it suitable for problems with large ranges.
Cons
The sorting step takes O(N log N) time, which might be slower than linear-time solutions if N is very large (though not for the given constraints).
The most efficient approach for this problem's constraints is using a difference array, a technique often associated with line sweep algorithms. Instead of tracking coverage for each point individually, we record the changes in coverage at the start and end points of each interval. By processing these changes sequentially, we can determine the coverage level at any point in linear time relative to the range of numbers.
Algorithm
- Create an integer array
diffof size 52, initialized to all zeros. This will be our difference array. - Iterate through each interval
[start, end]inranges. - For each interval, increment
diff[start]by 1. - Decrement
diff[end + 1]by 1 (ifend + 1is within the array bounds). This marks the end of the interval's influence. - After processing all ranges, perform a line sweep. Initialize a counter
currentCoverage = 0. - Iterate from
i = 1up toright. - In each step, update the coverage at point
iby adding the change:currentCoverage += diff[i]. - If the current point
iis within our target range (i.e.,i >= left) andcurrentCoverageis 0, it meansiis not covered by any interval. Returnfalse. - If the loop finishes up to
rightwithout finding any uncovered points, it means the entire range is covered. Returntrue.
Walkthrough
This technique hinges on a clever observation. An interval [start, end] increases the coverage count for all numbers from start onwards and decreases it for all numbers from end + 1 onwards. We can model this using a difference array, diff. We iterate through ranges, and for each [start, end], we do diff[start]++ and diff[end + 1]--. After setting up this diff array, the actual number of intervals covering any point i can be found by summing up all diff[j] for j <= i. We can compute this prefix sum on the fly. We iterate from 1 to right, maintaining a running sum currentCoverage. For each i, we update currentCoverage += diff[i]. If at any point i is within [left, right] and currentCoverage is 0, we've found an uncovered integer and return false.
class Solution { public boolean isCovered(int[][] ranges, int left, int right) { // Difference array. Size 52 for numbers 1-50 and endpoint 51. int[] diff = new int[52]; for (int[] range : ranges) { int start = range[0]; int end = range[1]; diff[start]++; if (end + 1 < 52) { diff[end + 1]--; } } // Perform line sweep to calculate coverage at each point. int currentCoverage = 0; for (int i = 1; i < 52; i++) { currentCoverage += diff[i]; // If a number within the target range is not covered, return false. if (i >= left && i <= right && currentCoverage == 0) { return false; } } return true; }}Complexity
Time
O(N + K), where N is the number of ranges and K is the maximum coordinate value. O(N) to build the difference array and O(K) for the line sweep.
Space
O(K), where K is the maximum possible value of a coordinate (51 in this case), for the difference array.
Trade-offs
Pros
Highly efficient, with a linear time complexity of O(N + K).
It is the asymptotically fastest solution for the given constraints.
Cons
Requires extra space proportional to the maximum coordinate value.
Can be less intuitive than more direct approaches if unfamiliar with the technique.
Solutions
Solution
class Solution {public boolean isCovered(int[][] ranges, int left, int right) { int[] diff = new int[52]; for (int[] range : ranges) { int l = range[0], r = range[1]; ++diff[l]; --diff[r + 1]; } int cur = 0; for (int i = 0; i < diff.length; ++i) { cur += diff[i]; if (i >= left && i <= right && cur == 0) { return false; } } return true; }}/** * @param {number[][]} ranges * @param {number} left * @param {number} right * @return {boolean} */ var isCovered = function (ranges, left, right) { const diff = new Array(52).fill(0); for (const [l, r] of ranges) { ++diff[l]; --diff[r + 1]; } let cur = 0; for (let i = 0; i < 52; ++i) { cur += diff[i]; if (i >= left && i <= right && cur <= 0) { return false; } } return true; };class Solution {public: bool isCovered(vector<vector<int>> &ranges, int left, int right) { int diff[52]{}; for (auto &range : ranges) { int l = range[0], r = range[1]; ++diff[l]; --diff[r + 1]; } int cur = 0; for (int i = 0; i < 52; ++i) { cur += diff[i]; if (i >= left && i <= right && cur <= 0) { return false; } } return true; }};class Solution: def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool: diff = [0] * 52 for l, r in ranges: diff[l] += 1 diff[r + 1] -= 1 cur = 0 for i, x in enumerate(diff): cur += x if left <= i <= right and cur == 0: return False return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.