Problem Description

You are given a 2D integer array ranges where each element ranges[i] = [start_i, end_i] represents an inclusive interval from start_i to end_i. You are also given two integers left and right that define another inclusive interval [left, right].

Your task is to determine whether every integer in the interval [left, right] is covered by at least one interval from the ranges array.

An integer x is considered covered by an interval ranges[i] = [start_i, end_i] if start_i <= x <= end_i.

Return true if every integer from left to right (inclusive) is covered by at least one interval in ranges. Otherwise, return false.

For example:

• If ranges = [[1, 3], [5, 7]] and we need to check interval [2, 6], the answer would be false because the integer 4 is not covered by any interval in ranges.
• If ranges = [[1, 10], [10, 20]] and we need to check interval [5, 15], the answer would be true because every integer from 5 to 15 is covered by at least one of the given intervals.

Intuition

To check if every integer in [left, right] is covered, we need to know which positions are covered by the intervals in ranges. A straightforward approach would be to mark each covered position, but instead of explicitly marking every single integer, we can use a more efficient technique.

Think of the coverage as a timeline where intervals can overlap. When an interval [l, r] starts at position l, the coverage count increases by 1. When it ends after position r, the coverage count decreases by 1. This is the key insight - we only need to track where coverage changes happen, not every single covered position.

This leads us to the difference array technique. Instead of storing the actual coverage count at each position, we store the changes in coverage. When we add an interval [l, r]:

• At position l, coverage increases (we add +1 to diff[l])
• At position r + 1, coverage decreases (we add -1 to diff[r + 1])

By accumulating these differences as we scan through the positions, we can reconstruct the actual coverage count at any position. If at any position i within [left, right] the accumulated coverage count becomes 0 or negative, it means that position is not covered by any interval.

The beauty of this approach is that we only need to process each interval once to update the difference array, and then make a single pass to check coverage, making it very efficient compared to checking each integer individually against all intervals.

Learn more about Prefix Sum patterns.

Solution Approach

We implement the solution using a difference array technique:

1. Initialize the difference array: Create a difference array diff of size 52. We use 52 to safely handle the constraint range (the problem typically has values between 1 and 50, so 52 provides enough buffer).

2. Build the difference array: For each interval [l, r] in ranges:

   • Increment diff[l] by 1 to mark the start of coverage
   • Decrement diff[r + 1] by 1 to mark the end of coverage

   This step processes all intervals and records where coverage changes occur.

3. Check coverage using prefix sum: Iterate through the difference array while maintaining a running sum s:

   • For each position i, add diff[i] to the sum: s += diff[i]
   • The value of s at position i represents the number of intervals covering position i
   • If s <= 0 and i is within [left, right] (i.e., left <= i <= right), it means position i is not covered by any interval, so return False

4. Return the result: If we complete the iteration without finding any uncovered position in [left, right], return True.

The algorithm efficiently determines coverage by tracking only the points where coverage changes, rather than checking every single position against every interval. The time complexity is O(n + m) where n is the number of intervals and m is the range of values, and the space complexity is O(m) for the difference array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example:

• ranges = [[1, 2], [3, 4], [5, 6]]
• We need to check if interval [2, 5] is fully covered

Step 1: Initialize the difference array We create a difference array diff of size 52, initially all zeros:

diff = [0, 0, 0, 0, 0, 0, 0, ...] (52 zeros)

Step 2: Build the difference array For each interval in ranges, we mark where coverage starts and ends:

• For interval [1, 2]:

  • diff[1] += 1 (coverage starts at 1)
  • diff[3] -= 1 (coverage ends after 2)

• For interval [3, 4]:

  • diff[3] += 1 (coverage starts at 3)
  • diff[5] -= 1 (coverage ends after 4)

• For interval [5, 6]:

  • diff[5] += 1 (coverage starts at 5)
  • diff[7] -= 1 (coverage ends after 6)

After processing all intervals:

Index: 0  1  2  3  4  5  6  7  8...
diff:  0  1  0  0  0  0  0 -1  0...
       ↑  ↑     ↑     ↑     ↑
       0  +1    -1+1  0    +1-1
Final: 0  1  0  0  0  0  0 -1  0...

Step 3: Check coverage using prefix sum Now we traverse the difference array, maintaining a running sum to get actual coverage:

• Position 0: sum = 0 + 0 = 0
• Position 1: sum = 0 + 1 = 1 (1 interval covers position 1)
• Position 2: sum = 1 + 0 = 1 (1 interval covers position 2) ✓ (in [2,5])
• Position 3: sum = 1 + 0 = 1 (1 interval covers position 3) ✓ (in [2,5])
• Position 4: sum = 1 + 0 = 1 (1 interval covers position 4) ✓ (in [2,5])
• Position 5: sum = 1 + 0 = 1 (1 interval covers position 5) ✓ (in [2,5])

All positions in [2, 5] have coverage count ≥ 1, so we return true.

Counter-example to see when it fails: If we had ranges = [[1, 2], [4, 5]] and needed to check [2, 5]:

• After building diff array and computing prefix sums:
  • Position 2: coverage = 1 ✓
  • Position 3: coverage = 0 ✗ (not covered!)
  • Position 4: coverage = 1 ✓
  • Position 5: coverage = 1 ✓

Since position 3 has no coverage and is within [2, 5], we would return false.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + M), where n is the length of the array ranges and M is the size of the difference array (which is 52 in this implementation, representing the maximum possible range value plus some buffer).

• The first loop iterates through all n ranges to update the difference array, taking O(n) time.
• The second loop iterates through the entire difference array of size M to compute prefix sums and check conditions, taking O(M) time.
• Since these operations are sequential, the total time complexity is O(n + M).

The space complexity is O(M), where M = 52 in this case.

• The difference array diff has a fixed size of 52 elements, requiring O(52) = O(M) space.
• All other variables (s, i, x, l, r) use constant space O(1).
• Therefore, the overall space complexity is O(M).

Since the problem constraints limit the interval values to be at most 50, we have M ≤ 50 (with some buffer in the implementation), making both complexities effectively O(n + 50) for time and O(50) for space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Difference Array Updates

A critical pitfall is incorrectly updating the difference array boundaries. Many developers mistakenly write:

• difference_array[end] -= 1 instead of difference_array[end + 1] -= 1

This error causes the coverage to end one position too early. Since the intervals are inclusive (meaning [start, end] includes both start and end), we need to decrement at position end + 1 to ensure position end remains covered.

Example of the bug:

# WRONG: This makes position 'end' uncovered
difference_array[start] += 1
difference_array[end] -= 1  # Bug: should be end + 1

Solution: Always remember that for inclusive intervals, the decrement happens at end + 1.

2. Incorrect Coverage Check Logic

Another common mistake is using the wrong comparison operator when checking coverage:

# WRONG: This checks for "more than zero coverage"
if cumulative_coverage < 0 and left <= position <= right:
    return False

The correct check should be cumulative_coverage <= 0 because a position needs at least one interval covering it (coverage > 0). A coverage of exactly 0 means no interval covers that position.

Solution: Use <= 0 to check for lack of coverage, not just < 0.

3. Array Size and Index Out of Bounds

Using an array size that's too small can cause index out of bounds errors:

# WRONG: Array too small for the constraints
difference_array = [0] * 51  # May cause IndexError if end = 50

Since we access difference_array[end + 1], and end can be up to 50, we need at least size 52.

Solution: Always allocate sufficient space considering the maximum possible index access. Using size 52 provides a safe buffer for the typical constraint range [1, 50].

4. Checking Coverage Before Building Complete Difference Array

Some implementations try to check coverage while building the difference array:

# WRONG: Checking coverage while still building the array
for start, end in ranges:
    difference_array[start] += 1
    difference_array[end + 1] -= 1
    # Don't check coverage here - array is incomplete!

The difference array must be completely built before calculating cumulative sums and checking coverage.

Solution: Separate the array building phase from the coverage checking phase. Complete all range updates first, then perform the cumulative sum and coverage verification.