{x}
blog image

Check if All the Integers in a Range Are Covered

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

Solution Explanation: Check if All Integers in a Range Are Covered

This problem asks whether every integer in the range [left, right] is included in at least one of the given intervals in ranges. A naive approach would involve iterating through each number in the range and checking if it's covered, but this is inefficient. A more optimal approach utilizes a difference array.

Difference Array Approach

The core idea is to represent the coverage of integers using a difference array. We create a difference array diff of size 52 (because the maximum value is 50, we need an extra space to accommodate the last interval). Each index i in diff will represent the integer i.

  1. Initialization: We initialize diff with zeros.

  2. Interval Processing: For each interval [start, end] in ranges, we increment diff[start] by 1 and decrement diff[end + 1] by 1. This is the key step. The cumulative sum of diff will represent the number of intervals covering each integer.

  3. Cumulative Sum: We iterate through diff and calculate the cumulative sum s. For each index i, s represents the number of intervals covering integer i.

  4. Checking Coverage: If at any point s becomes less than or equal to 0 and we're within the range [left, right], it means that integer i is not covered by any interval, so we return false.

  5. Return True: If we reach the end of the iteration without finding any uncovered integers in the specified range, we return true.

Time and Space Complexity

  • Time Complexity: O(n + M), where n is the number of ranges and M is the maximum value (50 in this problem). The algorithm iterates through the ranges once and the difference array once.

  • Space Complexity: O(M), where M is the maximum value. The space complexity is dominated by the difference array.

Code Examples (Python, Java, C++, Go, TypeScript, JavaScript)

The code examples below demonstrate this approach in various programming languages. They all follow the same core logic: create a difference array, process intervals, calculate cumulative sum, and check for coverage.

Python3:

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
        s = 0
        for i, x in enumerate(diff):
            s += x
            if s <= 0 and left <= i <= right:
                return False
        return True

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 s = 0;
        for (int i = 0; i < diff.length; ++i) {
            s += diff[i];
            if (s <= 0 && left <= i && i <= right) {
                return false;
            }
        }
        return true;
    }
}

C++:

class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        vector<int> diff(52);
        for (auto& range : ranges) {
            int l = range[0], r = range[1];
            ++diff[l];
            --diff[r + 1];
        }
        int s = 0;
        for (int i = 0; i < diff.size(); ++i) {
            s += diff[i];
            if (s <= 0 && left <= i && i <= right) {
                return false;
            }
        }
        return true;
    }
};

Go:

func isCovered(ranges [][]int, left int, right int) bool {
	diff := [52]int{}
	for _, e := range ranges {
		l, r := e[0], e[1]
		diff[l]++
		diff[r+1]--
	}
	s := 0
	for i, x := range diff {
		s += x
		if s <= 0 && left <= i && i <= right {
			return false
		}
	}
	return true
}

TypeScript:

function isCovered(ranges: number[][], left: number, right: number): boolean {
    const diff: number[] = new Array(52).fill(0);
    for (const [l, r] of ranges) {
        diff[l]++;
        diff[r + 1]--;
    }
    let s = 0;
    for (let i = 0; i < diff.length; i++) {
        s += diff[i];
        if (s <= 0 && left <= i && i <= right) {
            return false;
        }
    }
    return true;
}

JavaScript:

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 s = 0;
    for (let i = 0; i < diff.length; i++) {
        s += diff[i];
        if (s <= 0 && left <= i && i <= right) {
            return false;
        }
    }
    return true;
};

These code examples all implement the difference array approach, providing efficient solutions to the problem. Remember that the size of the difference array (52 in these examples) needs to be adjusted if the input ranges can have larger values.