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 <= 501 <= starti <= endi <= 501 <= left <= right <= 50In #1893 Check if All the Integers in a Range Are Covered, you are given several integer ranges and must verify whether every number within a target interval [left, right] appears in at least one of those ranges. The core idea is to track which numbers are covered and ensure none in the required interval are missing.
A straightforward method is to use a boolean or counting array. For each range, mark the numbers it covers. After processing all ranges, iterate from left to right and check whether each value has been marked. If any number is uncovered, the answer is false.
An optimized way uses a prefix sum (difference array) technique. Instead of marking every element in a range, you update boundaries and compute cumulative coverage using prefix sums. This reduces repeated updates for overlapping ranges and keeps the solution efficient.
Both approaches rely on arrays for constant-time lookups, making the solution simple and efficient for the given constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Direct Array Marking | O(n * range) | O(1) to O(50) depending on constraints |
| Prefix Sum (Difference Array) | O(n + range) | O(range) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Iterate over every integer point in the range [left, right].
For each of these points check if it is included in one of the ranges.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums allow you to efficiently process multiple overlapping ranges without repeatedly updating every element. By marking range boundaries and computing cumulative sums, you can quickly determine how many times each index is covered.
While this exact problem may not always appear, similar interval coverage and range-checking questions are common in coding interviews at FAANG-level companies. They often test understanding of arrays, prefix sums, and range processing techniques.
An array is typically the best data structure for this problem because the integer range is small and fixed. Arrays allow constant-time updates and checks, making them ideal for both direct marking and prefix sum approaches.
A common optimal approach uses a prefix sum (difference array) technique. Instead of marking each value in every range, you update only the start and end boundaries and compute coverage using cumulative sums. This reduces redundant updates and keeps the solution efficient.