Scale Engineer

Check if All the Integers in a Range Are Covered

Easy
#1727Time: 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.
Patterns
Prefix Sum
Data structures
ArrayHash Table

Prompt

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 <= 50
  • 1 <= starti <= endi <= 50
  • 1 <= 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

  1. Iterate through each integer i from left to right.
  2. For each integer i, assume it's not covered by setting a flag isCovered = false.
  3. Iterate through every interval [start, end] in the ranges array.
  4. If i falls within the current interval (i.e., start <= i <= end), set isCovered = true and break the inner loop, as we've found a cover for i.
  5. After checking all ranges, if the isCovered flag is still false, it means the integer i is not covered by any interval. In this case, we can immediately conclude that not all integers are covered, so we return false.
  6. If the outer loop completes without returning false, it means every integer from left to right was successfully found in at least one interval. Return true.

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 the ranges array for each number in the target range.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem