Check if All the Integers in a Range Are Covered - Solution & Explanation
Problem Statement
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 <= 50
Approach Overview
Problem Overview: You receive a list of integer ranges and two numbers left and right. The task is to verify whether every integer in the interval [left, right] appears in at least one of the provided ranges.
Approach 1: Direct Range Check (Time: O(n * m), Space: O(1))
Iterate through every integer from left to right. For each value, scan all ranges and check whether the number falls inside any interval [start, end]. If a number is not covered by any range, return false immediately. The key idea is brute-force verification: treat each integer independently and validate coverage using simple comparisons. This works well because the constraints are small and avoids extra memory. You only perform range comparisons using standard array traversal.
Approach 2: Boolean Array Coverage (Time: O(n + U), Space: O(U))
Create a boolean array that represents whether each integer is covered. For every range [start, end], mark all indices between them as true. After processing all ranges, iterate from left to right and check if every position is marked. If any position is false, the required interval is not fully covered. This converts repeated range checks into constant-time lookups. The idea resembles coverage tracking often used in hash table style presence checks, and it can also be optimized with a difference array and prefix sum technique when ranges become larger.
Recommended for interviews: The boolean coverage approach is usually preferred because it reduces repeated scanning of ranges and clearly demonstrates interval coverage logic. The direct range check still shows good baseline reasoning and is acceptable when constraints are small, but the coverage array highlights your ability to trade memory for faster lookups.
Approach 1: Direct Range Check
This approach involves iterating through each number between left and right to check if it is covered by at least one range in ranges. For each number, we loop through all ranges, and as soon as we find a range that covers the number, we move to the next number. If any number isn't covered after checking all ranges, we return false.
We iterate over each number from left to right and check if it falls within any given range. If we find such a range, we proceed to the next number; otherwise, we return false.
Complexity
Time Complexity: O(n * m), where n is the number of integers from left to right and m is the number of ranges.
Space Complexity: O(1), no additional space is used besides the input.
Approach 2: Boolean Array Coverage
This method involves using a boolean array where each index indicates whether the corresponding number is covered. After initializing the array, we iterate over each range and mark the numbers within that range as covered in the boolean array. At the end, we check if all numbers from left to right are marked as covered.
The solution constructs a boolean array initialized as false representing number coverage from 1 to 50. As it iterates over each range, it updates the array indices to true for covered numbers.
Complexity
Time Complexity: O(m + n), with m as the number of ranges and n as the length of the boolean array (fixed at 50).
Space Complexity: O(1), using a constant-sized boolean array.
Approach 3: Difference Array
We can use the idea of a difference array to create a difference array diff of length 52.
Next, we iterate through the array ranges. For each interval [l, r], we increment diff[l] by 1 and decrement diff[r + 1] by 1.
Then, we iterate through the difference array diff, maintaining a prefix sum s. For each position i, we increment s by diff[i]. If s \le 0 and left \le i \le right, it indicates that an integer i within the interval [left, right] is not covered, and we return false.
If we finish iterating through the difference array diff without returning false, it means that every integer within the interval [left, right] is covered by at least one interval in ranges, and we return true.
The time complexity is O(n + M), and the space complexity is O(M). Here, n is the length of the array ranges, and M is the maximum value of the interval, which in this case is M \le 50.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Direct Range Check | Time Complexity: O(n * m), where n is the number of integers from Space Complexity: O(1), no additional space is used besides the input. |
| Boolean Array Coverage | Time Complexity: O(m + n), with m as the number of ranges and n as the length of the boolean array (fixed at 50). Space Complexity: O(1), using a constant-sized boolean array. |
| Difference Array | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Range Check | O(n * m) | O(1) | When constraints are small and you want the simplest brute-force logic |
| Boolean Array Coverage | O(n + U) | O(U) | Preferred when you want faster lookups for coverage checks across the interval |
Video Solution
Leetcode 1893 Check if All the Integers in a Range Are Covered • Sandip Jana • 1,407 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Check if All the Integers in a Range Are Covered easy or hard?
Check if All the Integers in a Range Are Covered Python/Java solution
How to solve Check if All the Integers in a Range Are Covered in O(n)?
What is the best approach for Check if All the Integers in a Range Are Covered?
Is Check if All the Integers in a Range Are Covered asked at Google/Amazon/Meta?
What data structure is used in Check if All the Integers in a Range Are Covered?
What is the time complexity of Check if All the Integers in a Range Are Covered?
Ready to solve this problem?
Practice Check if All the Integers in a Range Are Covered with our built-in code editor and test cases.
Practice on FleetCode