Check if All the Integers in a Range Are Covered

Easy
1110.

Check if All the Integers in a Range Are Covered

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.

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 <= 50
  • 1 <= start <= end <= 50
  • 1 <= left <= right <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} ranges
 * @param {number} left
 * @param {number} right
 * @return {boolean}
 */
var isCovered = function(ranges, left, right) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 50
  • 1 <= start <= end <= 50
  • 1 <= left <= right <= 50

Hints for Check if All the Integers in a Range Are Covered

  1. Hint 1

    The values are tiny (at most 50), so you can afford to look at each integer separately.

  2. Hint 2

    Instead of testing each integer against every interval, mark the coverage once.

  3. Hint 3

    A difference array: +1 at start, -1 at end + 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

  1. Create diff of size 52 filled with 0.
  2. For each interval, add 1 at diff[start] and subtract 1 at diff[end + 1].
  3. Sweep v from 1 to right, keeping the running sum cover.
  4. If some v >= left has cover == 0, return false; otherwise return true.

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, not end.
  • The sweep must start at 1, not at left, so intervals that begin before left are 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 True

Java

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