Check if All the Integers in a Range Are Covered

Difficulty: Easy | Acceptance: 51.00% | Paid: No Topics: Array, Hash Table, Prefix Sum

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 every integer in the inclusive range [left, right] is covered by at least one interval in ranges. Otherwise, return false.

• Examples
• Constraints
• Brute Force with Hash Set
• Prefix Sum / Difference Array
• Sorting + Interval Merging

Examples

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 range [1,2]
- 3 and 4 are covered by the range [3,4]
- 5 is covered by the range [5,6]

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

Brute Force with Hash Set

Intuition Store all covered integers from all ranges in a hash set, then verify every integer in the query range exists in the set.

Steps

• Iterate through each range and add all integers to a hash set
• Check if every integer from left to right exists in the set
• Return false if any integer is missing, true otherwise

class Solution:
    def isCovered(self, ranges: list[list[int]], left: int, right: int) -> bool:
        covered = set()
        for start, end in ranges:
            for num in range(start, end + 1):
                covered.add(num)
        for num in range(left, right + 1):
            if num not in covered:
                return False
        return True

Complexity

• Time: O(n × m) where n is number of ranges and m is average range length
• Space: O(n × m) for storing all covered integers
• Notes: Simple and intuitive, but uses extra space proportional to total covered values

Prefix Sum / Difference Array

Intuition Use a difference array to mark range starts and ends, then compute prefix sum to find which positions are covered by at least one range.

Steps

• Initialize a difference array of size 52 (since values go up to 50)
• For each range, increment at start index and decrement at end + 1
• Compute prefix sum while iterating through the array
• Check if all positions from left to right have prefix sum > 0

class Solution:
    def isCovered(self, ranges: list[list[int]], left: int, right: int) -> bool:
        diff = [0] * 52
        for start, end in ranges:
            diff[start] += 1
            if end + 1 < 52:
                diff[end + 1] -= 1
        
        prefix = 0
        for i in range(1, 52):
            prefix += diff[i]
            if left <= i <= right and prefix == 0:
                return False
        return True

Complexity

• Time: O(n + k) where n is number of ranges and k is the maximum value (50)
• Space: O(k) for the difference array
• Notes: Efficient for small value ranges, handles overlapping ranges elegantly

Sorting + Interval Merging

Intuition Sort ranges by start position, then greedily check if the query range can be covered by consecutive or overlapping intervals.

Steps

• Sort all ranges by their start value
• Initialize current pointer to left
• Iterate through sorted ranges, advancing current when covered
• If a gap is found between current and the next range, return false
• Return true if current exceeds right

class Solution:
    def isCovered(self, ranges: list[list[int]], left: int, right: int) -> bool:
        ranges.sort(key=lambda x: x[0])
        
        i = 0
        n = len(ranges)
        current = left
        
        while current <= right and i < n:
            if ranges[i][0] <= current <= ranges[i][1]:
                current = ranges[i][1] + 1
                i += 1
            elif ranges[i][1] < current:
                i += 1
            else:
                return False
        
        return current > right

Complexity

• Time: O(n log n) for sorting
• Space: O(1) or O(n) depending on sorting implementation
• Notes: Most efficient for large value ranges, handles arbitrary integer values