LeetCode 1893 - Check if All the Integers in a Range Are Covered

The problem asks us to determine whether every integer within a given inclusive range [left, right] is covered by at least one of the intervals specified in the ranges array.

leetcodeeasyarrayhash-tableprefix-sum

LeetCode Problem 1893

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine whether every integer within a given inclusive range [left, right] is covered by at least one of the intervals specified in the ranges array. Each element of ranges is itself an array [starti, endi] representing an inclusive interval, meaning the integers starti and endi are part of the interval. The input consists of up to 50 intervals and numbers ranging from 1 to 50 for both the interval endpoints and the target range. This guarantees a very small input size, which allows us to consider solutions that might not scale for larger ranges.

The output is a boolean value: true if every integer between left and right is included in at least one interval, and false if any integer is missing from all intervals. Edge cases to consider include when left and right are the same number, intervals that overlap, and intervals that cover ranges partially outside [left, right].

Important edge cases include ranges that exactly cover [left, right], ranges that overshoot on one or both sides, and ranges that are disjoint or skip numbers inside [left, right].

Approaches

A brute-force approach involves iterating over every integer from left to right and checking whether it appears in any of the intervals. This is guaranteed to be correct but requires checking up to 50 numbers against up to 50 ranges, giving a worst-case complexity of O(50*50), which is acceptable for the constraints but not the most elegant solution.

The optimal approach leverages a boolean array to mark which integers from 1 to 50 are covered. For each interval [starti, endi], we mark all integers within that interval as covered. After processing all intervals, we iterate over [left, right] and check if all these numbers are marked. This approach is straightforward, efficient, and leverages the small input domain.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*m) O(1) Check each number in [left, right] against all intervals
Optimal O(n + m) O(50) Use a boolean array to mark coverage for integers 1 to 50

Here, n is the number of intervals in ranges, and m is the size of the target range right - left + 1.

Algorithm Walkthrough

  1. Initialize a boolean array covered of size 51 (to include 1-50) with all values set to False. Each index represents whether that integer is covered.
  2. Iterate over each interval [starti, endi] in ranges. For each interval, iterate from starti to endi inclusive, marking each number in the covered array as True.
  3. After all intervals have been processed, iterate through the integers from left to right. For each integer, check whether it is marked True in the covered array.
  4. If all integers in [left, right] are covered, return True. Otherwise, return False.

This works because the boolean array ensures that each integer is checked exactly once for coverage. The invariant is that after processing all intervals, covered[i] is True if and only if the integer i is contained in at least one interval.

Python Solution

from typing import List

class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        covered = [False] * 51  # 1-based indexing for numbers 1 to 50
        for start, end in ranges:
            for i in range(start, end + 1):
                covered[i] = True
        for num in range(left, right + 1):
            if not covered[num]:
                return False
        return True

The Python implementation initializes a boolean array to mark covered numbers. It iterates through each range and marks all numbers in that range as True. Finally, it checks each number in [left, right] and returns False immediately if any number is uncovered. If all are covered, it returns True.

Go Solution

func isCovered(ranges [][]int, left int, right int) bool {
    covered := [51]bool{}  // 1-based indexing for numbers 1 to 50
    for _, r := range ranges {
        for i := r[0]; i <= r[1]; i++ {
            covered[i] = true
        }
    }
    for i := left; i <= right; i++ {
        if !covered[i] {
            return false
        }
    }
    return true
}

In Go, we use a fixed-size array of 51 booleans. We iterate through each interval and mark the numbers as covered. Checking [left, right] for uncovered numbers works identically to Python. Go handles arrays and slices efficiently, and there is no need for dynamic allocation due to the fixed input constraints.

Worked Examples

Example 1: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5

Step Operation covered array snapshot
1 mark [1,2] True at indices 1,2
2 mark [3,4] True at indices 3,4
3 mark [5,6] True at indices 5,6
4 check 2 covered[2] = True
5 check 3 covered[3] = True
6 check 4 covered[4] = True
7 check 5 covered[5] = True
8 all covered return True

Example 2: ranges = [[1,10],[10,20]], left = 21, right = 21

Step Operation covered array snapshot
1 mark [1,10] True at indices 1-10
2 mark [10,20] True at indices 10-20
3 check 21 covered[21] = False
4 not covered return False

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Marking all intervals takes O(n*length_of_intervals) but max interval length is 50, checking [left, right] is O(m)
Space O(50) Fixed-size boolean array to track coverage

Since the numbers are bounded by 50, this is effectively constant space and linear time relative to the number of intervals and target range length.

Test Cases

# test cases
assert Solution().isCovered([[1,2],[3,4],[5,6]], 2, 5) == True  # covers all numbers 2–5
assert Solution().isCovered([[1,10],[10,20]], 21, 21) == False  # 21 not covered
assert Solution().isCovered([[1,50]], 1, 50) == True  # single range covers entire range
assert Solution().isCovered([[1,25],[26,50]], 1, 50) == True  # split range covers exactly 1–50
assert Solution().isCovered([[1,10],[12,20]], 9, 12) == False  # missing 11
assert Solution().isCovered([[5,5]], 5, 5) == True  # single number range
assert Solution().isCovered([[1,2]], 2, 3) == False  # partial coverage, missing 3
Test Why
[[1,2],[3,4],[5,6]], 2, 5 Tests normal multiple intervals
[[1,10],[10,20]], 21, 21 Tests number not covered
[[1,50]], 1, 50 Single interval covering full range
[[1,25],[26,50]], 1, 50 Edge of split intervals covering full range
[[1,10],[12,20]], 9, 12 Checks gap in coverage
[[5,5]], 5, 5 Minimal single-number interval
[[1,2]], 2, 3 Partial coverage, last number missing

Edge Cases

One important edge case is when left equals right. This represents a single number. The algorithm handles it correctly because it still checks this number in the final loop.

A second edge case is when intervals overlap, such as [1,10] and [5,15]. The boolean marking ensures that overlapping coverage does not cause any double-counting or missed numbers. Each number is marked as covered at least once.

A third edge case is when ranges are outside [left, right], such as [1,2] with left = 3. The algorithm correctly ignores these because the final check only evaluates [left, right], so numbers outside this range do not affect the result.