# Check if All the Integers in a Range Are Covered
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-all-the-integers-in-a-range-are-covered)
Canonical: https://scaleengineer.com/dsa/problems/check-if-all-the-integers-in-a-range-are-covered
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## Problem
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
## 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`.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Marking Covered Numbers in an Array
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`.
**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).
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
1. Create a boolean array, `covered`, of size 52 (to handle numbers up to 50), and initialize all its elements to `false`.
2. Iterate through each interval `[start, end]` in the `ranges` array.
3. For each interval, run a loop from `start` to `end`. In this loop, mark every integer `j` as covered by setting `covered[j] = true`.
4. After populating the `covered` array, iterate through the target range from `left` to `right`.
5. For each integer `i` in this range, check if `covered[i]` is `true`.
6. If `covered[i]` is `false` for any `i`, it means that number is not covered. Return `false`.
7. If the loop completes, it means all numbers in the range `[left, right]` are covered. Return `true`.

## Greedy Approach with Sorting
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.
**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.
**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).
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Sort the `ranges` array 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.
2. Initialize a variable `covered_reach` to `left - 1`. This variable will track the maximum integer we have covered so far, starting from the beginning of our target range.
3. Iterate through the sorted `ranges`.
4. For each `range = [start, end]`:
   - If the `start` of the current range is greater than `covered_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. Update `covered_reach = max(covered_reach, end)`.
   - After updating `covered_reach`, check if `covered_reach >= right`. If it is, we have successfully covered the entire target range, and we can return `true`.
5. If the loop finishes, we make one final check: `return covered_reach >= right`.

## Difference Array (Line Sweep)
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
1. Create an integer array `diff` of size 52, initialized to all zeros. This will be our difference array.
2. Iterate through each interval `[start, end]` in `ranges`.
3. For each interval, increment `diff[start]` by 1.
4. Decrement `diff[end + 1]` by 1 (if `end + 1` is within the array bounds). This marks the end of the interval's influence.
5. After processing all ranges, perform a line sweep. Initialize a counter `currentCoverage = 0`.
6. Iterate from `i = 1` up to `right`.
7. In each step, update the coverage at point `i` by adding the change: `currentCoverage += diff[i]`.
8. If the current point `i` is within our target range (i.e., `i >= left`) and `currentCoverage` is 0, it means `i` is not covered by any interval. Return `false`.
9. If the loop finishes up to `right` without finding any uncovered points, it means the entire range is covered. Return `true`.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @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;
  };

```

### CPP

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

```

### Python

```python
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 True

```