Check if All the Integers in a Range Are Covered solution and explanation
7 more videos on this problem
Leetcode 1893 Check if All the Integers in a Range Are CoveredSandip Jana · 7:10 · 1K views
1893. Check if All the Integers in a Range Are Covered | LEETCODE EASYcode Explainer · 4:53 · 1K views
1893. Check if All the Integers in a Range Are Covered (Leetcode Easy)Programming Live with Larry · 2:52 · 1K views
【每日一题】LeetCode 1893. Check if All the Integers in a Range Are CoveredHuifeng Guan · 8:45 · 543 views
Check if All the Integers in a Range Are Covered || LeetCode Biweekly Contest 54 || Java SolutionGeek's Space · 10:24 · 390 views
Leetcode 1893. Check if All the Integers in a Range Are Covered (difference array)LetsCode · 2:48 · 151 views
LeetCode 1893: Check if All Integers in a Range Are Covered | Python Solution Explained Step-by-StepCoding with Seattle Brandon · 2:33 · 128 views
LeetCode 1893: Check if All the Integers in a Range Are CoveredAlitaCode · 26:29 · 5 views
The problem
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.
class Solution:
def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
for num in range(left, right + 1):
if not any(start <= num <= end for start, end in ranges):
return False
return Trueclass Solution {
public boolean isCovered(int[][] ranges, int left, int right) {
for (int num = left; num <= right; num++) {
boolean covered = false;
for (int[] range : ranges) {
if (range[0] <= num && num <= range[1]) {
covered = true;
break;
}
}
if (!covered) return false;
}
return true;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool isCovered(vector<vector<int>>& ranges, int left, int right) {
for (int num = left; num <= right; ++num) {
bool covered = false;
for (auto& range : ranges) {
if (range[0] <= num && num <= range[1]) {
covered = true;
break;
}
}
if (!covered) return false;
}
return true;
}
};var isCovered = function(ranges, left, right) {
for (let num = left; num <= right; num++) {
let covered = false;
for (let range of ranges) {
if (range[0] <= num && num <= range[1]) {
covered = true;
break;
}
}
if (!covered) return false;
}
return true;
};#include <stdbool.h>
bool isCovered(int** ranges, int rangesSize, int* rangesColSize, int left, int right) {
for (int num = left; num <= right; ++num) {
bool covered = false;
for (int i = 0; i < rangesSize; ++i) {
if (ranges[i][0] <= num && num <= ranges[i][1]) {
covered = true;
break;
}
}
if (!covered) return false;
}
return true;
}public class Solution {
public bool IsCovered(int[][] ranges, int left, int right) {
for (int num = left; num <= right; num++) {
bool covered = false;
foreach (var range in ranges) {
if (range[0] <= num && num <= range[1]) {
covered = true;
break;
}
}
if (!covered) return false;
}
return true;
}
}This Python solution uses a list comprehension within any() to check if each number from left to right is covered by at least one range in ranges. It stops iteration as soon as a number is found not covered.
Time Complexity: O(n * m), where n refers to the count of integers between left and right, and m represents the number of ranges.
Space Complexity: O(1), straightforward iteration requiring no additional storage.
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.
class Solution:
def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
covered = [False] * 51
for start, end in ranges:
for num in range(start, end + 1):
covered[num] = True
for num in range(left, right + 1):
if not covered[num]:
return False
return Trueclass Solution {
public boolean isCovered(int[][] ranges, int left, int right) {
boolean[] covered = new boolean[51];
for (int[] range : ranges) {
for (int num = range[0]; num <= range[1]; num++) {
covered[num] = true;
}
}
for (int num = left; num <= right; num++) {
if (!covered[num]) return false;
}
return true;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool isCovered(vector<vector<int>>& ranges, int left, int right) {
vector<bool> covered(51, false);
for (auto& range : ranges) {
for (int num = range[0]; num <= range[1]; ++num) {
covered[num] = true;
}
}
for (int num = left; num <= right; ++num) {
if (!covered[num]) return false;
}
return true;
}
};var isCovered = function(ranges, left, right) {
const covered = Array(51).fill(false);
for (const [start, end] of ranges) {
for (let num = start; num <= end; num++) {
covered[num] = true;
}
}
for (let num = left; num <= right; num++) {
if (!covered[num]) return false;
}
return true;
};#include <stdbool.h>
#include <string.h>
bool isCovered(int** ranges, int rangesSize, int* rangesColSize, int left, int right) {
bool covered[51] = {false};
for (int i = 0; i < rangesSize; ++i) {
for (int num = ranges[i][0]; num <= ranges[i][1]; ++num) {
covered[num] = true;
}
}
for (int num = left; num <= right; ++num) {
if (!covered[num]) return false;
}
return true;
}public class Solution {
public bool IsCovered(int[][] ranges, int left, int right) {
bool[] covered = new bool[51];
foreach (var range in ranges) {
for (int num = range[0]; num <= range[1]; num++) {
covered[num] = true;
}
}
for (int num = left; num <= right; num++) {
if (!covered[num]) return false;
}
return true;
}
}Uses a fixed-size covered list to track coverage status from 1 through 50. Iterates over ranges to update coverage information accordingly.
Time Complexity: O(m + n), where m is the number of ranges, and n is effectively constant.
Space Complexity: O(1), as the coverage list's size is fixed.
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.
function isCovered(ranges: number[][], left: number, right: number): boolean {
const diff: number[] = Array(52).fill(0);
for (const [l, r] of ranges) {
++diff[l];
--diff[r + 1];
}
let s = 0;
for (let i = 0; i < diff.length; ++i) {
s += diff[i];
if (s <= 0 && left <= i && i <= right) {
return false;
}
}
return true;
}func isCovered(ranges [][]int, left int, right int) bool {
diff := [52]int{}
for _, e := range ranges {
l, r := e[0], e[1]
diff[l]++
diff[r+1]--
}
s := 0
for i, x := range diff {
s += x
if s <= 0 && left <= i && i <= right {
return false
}
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Direct Range Check | Time Complexity: O(n * m), where n refers to the count of integers between Space Complexity: O(1), straightforward iteration requiring no additional storage. |
| Boolean Array Coverage | Time Complexity: O(m + n), where m is the number of ranges, and n is effectively constant. Space Complexity: O(1), as the coverage list's size is fixed. |
| Difference Array | – |
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 |
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 is classified as an Easy problem. The logic mainly involves iterating through ranges and verifying interval coverage using arrays or simple marking techniques.
Check if All the Integers in a Range Are Covered Python/Java solution
In Python or Java, implement either a brute-force scan for each integer or build a boolean array that marks coverage for each range. After marking, iterate from left to right and ensure every value is covered.
How to solve Check if All the Integers in a Range Are Covered in O(n)?
Use a coverage array or difference array. Mark all integers that appear in the provided ranges, then verify that every integer between left and right is marked. This approach processes each range once and performs constant-time lookups for validation.
What is the best approach for Check if All the Integers in a Range Are Covered?
The boolean array coverage approach is typically the best. Mark each number covered by the given ranges and then verify that every integer from left to right is marked. This reduces repeated range scans and runs in O(n + U) time where U is the width of the target interval.
Is Check if All the Integers in a Range Are Covered asked at Google/Amazon/Meta?
Range coverage and interval validation problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying concepts of interval processing and prefix sum techniques are common interview topics.
What data structure is used in Check if All the Integers in a Range Are Covered?
The common data structure is a boolean array used to track whether each integer in the domain is covered. Some variations also use prefix sum arrays or hash-based presence checks depending on the size of the value range.
What is the time complexity of Check if All the Integers in a Range Are Covered?
The direct range check approach runs in O(n * m) time where n is the number of ranges and m is the size of the interval [left, right]. The optimized boolean coverage method runs in O(n + U) time where U = right - left + 1.