Check if All the Integers in a Range Are Covered

EASY

Description

You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [start_i, end_i] represents an inclusive interval between start_i and end_i.

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] = [start_i, end_i] if start_i <= x <= end_i.

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 <= start_i <= end_i <= 50
1 <= left <= right <= 50

Approaches

Checkout 4 different approaches to solve Check if All the Integers in a Range Are Covered. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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 i from left to right.
For each integer i, assume it's not covered by setting a flag isCovered = false.
Iterate through every interval [start, end] in the ranges array.
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.
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.
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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to keep track of the current state.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Check if All the Integers in a Range Are Covered. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Check if All the Integers in a Range Are Covered

Patterns:

Prefix Sum

Data Structures:

ArrayHash Table