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 byat least one interval in ranges. Return false otherwise.

An integer x is covered by an interval ranges[i] = [starti, endi] if starti <= x <= endi.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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

Method 1 – Prefix Sum Coverage Array

Intuition

If we mark all the numbers covered by the given ranges, we can quickly check if every number in [left, right] is covered. Using a prefix sum array allows us to efficiently mark and check coverage for all numbers in the range.

Approach

  1. Create an array cover of size 52 (since numbers go up to 50) initialized to 0.
  2. For each range [start, end], increment cover[start] and decrement cover[end+1].
  3. Compute the prefix sum of cover so that cover[i] tells if i is covered.
  4. For each number from left to right, check if cover[i] > 0. If any is not covered, return false.
  5. Return true if all are covered.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        int cover[52] = {0};
        for (auto& r : ranges) {
            cover[r[0]]++;
            cover[r[1]+1]--;
        }
        for (int i = 1; i < 52; ++i) cover[i] += cover[i-1];
        for (int i = left; i <= right; ++i) {
            if (cover[i] == 0) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func isCovered(ranges [][]int, left int, right int) bool {
    cover := make([]int, 52)
    for _, r := range ranges {
        cover[r[0]]++
        cover[r[1]+1]--
    }
    for i := 1; i < 52; i++ {
        cover[i] += cover[i-1]
    }
    for i := left; i <= right; i++ {
        if cover[i] == 0 {
            return false
        }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        int[] cover = new int[52];
        for (int[] r : ranges) {
            cover[r[0]]++;
            cover[r[1]+1]--;
        }
        for (int i = 1; i < 52; ++i) cover[i] += cover[i-1];
        for (int i = left; i <= right; ++i) {
            if (cover[i] == 0) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun isCovered(ranges: Array<IntArray>, left: Int, right: Int): Boolean {
        val cover = IntArray(52)
        for (r in ranges) {
            cover[r[0]]++
            cover[r[1]+1]--
        }
        for (i in 1 until 52) cover[i] += cover[i-1]
        for (i in left..right) {
            if (cover[i] == 0) return false
        }
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def isCovered(ranges: list[list[int]], left: int, right: int) -> bool:
    cover: list[int] = [0] * 52
    for s, e in ranges:
        cover[s] += 1
        cover[e+1] -= 1
    for i in range(1, 52):
        cover[i] += cover[i-1]
    for i in range(left, right+1):
        if cover[i] == 0:
            return False
    return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn is_covered(ranges: Vec<Vec<i32>>, left: i32, right: i32) -> bool {
        let mut cover = [0; 52];
        for r in ranges.iter() {
            cover[r[0] as usize] += 1;
            cover[(r[1]+1) as usize] -= 1;
        }
        for i in 1..52 {
            cover[i] += cover[i-1];
        }
        for i in left..=right {
            if cover[i as usize] == 0 {
                return false;
            }
        }
        true
    }
}

Complexity

  • ⏰ Time complexity: O(n + R), where n is the number of ranges and R is the size of the range (at most 50).
  • 🧺 Space complexity: O(1), since the array size is constant.