Check if All the Integers in a Range Are Covered — Solution
Check if All the Integers in a Range Are Covered solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check if All the Integers in a Range Are Covered is an easy coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
ranges[i] = [start, end] describes the inclusive interval of integers from start to end. An integer v is covered if at least one interval contains it (start <= v <= end).
Return true if every integer in the inclusive range [left, right] is covered.
Example 1
Input: ranges = [[2,4],[6,9]], left = 3, right = 7
Output: false
Explanation: 5 lies in neither interval.
Example 2
Input: ranges = [[1,5],[4,8]], left = 2, right = 8
Output: true
Example 3
Input: ranges = [[10,20]], left = 10, right = 10
Output: true
Constraints
1 <= ranges.length <= 501 <= start <= end <= 501 <= left <= right <= 50
Hints for Check if All the Integers in a Range Are Covered
Hint 1
The values are tiny (at most 50), so you can afford to look at each integer separately.
Hint 2
Instead of testing each integer against every interval, mark the coverage once.
Hint 3
A difference array: +1 at
start, -1 atend + 1; its running sum is how many intervals cover each integer.
How to solve Check if All the Integers in a Range Are Covered
A difference array turns all intervals into per-integer coverage counts in one sweep; then every integer from left to right must have a positive count.
Approach
- Create
diffof size 52 filled with 0. - For each interval, add 1 at
diff[start]and subtract 1 atdiff[end + 1]. - Sweep
vfrom 1 toright, keeping the running sumcover. - If some
v >= lefthascover == 0, returnfalse; otherwise returntrue.
Why it works
The running sum at v adds 1 for every interval that started at or before v and subtracts 1 for every one that ended before v, so it is exactly the number of intervals containing v. A positive value means covered.
Complexity
- Time —
O(n + R) with R = 50 - Space —
O(R)
Pitfalls
- Intervals are inclusive: the -1 goes at
end + 1, notend. - The sweep must start at 1, not at
left, so intervals that begin beforeleftare counted. - Overlapping intervals are fine — only whether the count is positive matters.
Reference solution
Python
from typing import List
def isCovered(ranges: List[List[int]], left: int, right: int) -> bool:
diff = [0] * 52
for s, e in ranges:
diff[s] += 1
diff[e + 1] -= 1
cover = 0
for v in range(1, right + 1):
cover += diff[v]
if v >= left and cover <= 0:
return False
return TrueJava
public static boolean isCovered(int[][] ranges, int left, int right) {
int[] diff = new int[52];
for (int[] r : ranges) {
diff[r[0]]++;
diff[r[1] + 1]--;
}
int cover = 0;
for (int v = 1; v <= right; v++) {
cover += diff[v];
if (v >= left && cover <= 0) return false;
}
return true;
}C++
bool isCovered(vector<vector<int>>& ranges, int left, int right) {
vector<int> diff(52, 0);
for (auto& r : ranges) {
diff[r[0]]++;
diff[r[1] + 1]--;
}
int cover = 0;
for (int v = 1; v <= right; v++) {
cover += diff[v];
if (v >= left && cover <= 0) return false;
}
return true;
}JavaScript
var isCovered = function(ranges, left, right) {
var diff = new Array(52).fill(0);
for (var i = 0; i < ranges.length; i++) {
diff[ranges[i][0]]++;
diff[ranges[i][1] + 1]--;
}
var cover = 0;
for (var v = 1; v <= right; v++) {
cover += diff[v];
if (v >= left && cover <= 0) return false;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets