Check if All the Integers in a Range Are Covered

Check if All the Integers in a Range Are Covered - Problem

You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [start_i, end_i] represents an inclusive interval between start_i and end_i.

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] = [start_i, end_i] if start_i <= x <= end_i.

Input & Output

Example 1 — Basic Coverage

$ Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5

› Output: true

💡 Note: Every integer 2,3,4,5 is covered: 2 is in [1,2], 3 is in [3,4], 4 is in [3,4], 5 is in [5,6]

Example 2 — Gap in Coverage

$ Input: ranges = [[1,10],[10,20]], left = 1, right = 21

› Output: false

💡 Note: Numbers 1-20 are covered by the ranges, but 21 is not covered by any range

Example 3 — Single Number Range

$ Input: ranges = [[1,1],[2,2],[3,3]], left = 1, right = 3

› Output: true

💡 Note: Each number 1,2,3 is exactly covered by its corresponding single-number range

Constraints

1 ≤ ranges.length ≤ 50
1 ≤ start_i ≤ end_i ≤ 50
1 ≤ left ≤ right ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Ranges [[1,2],[3,4],[5,6]] and target [2,5]

Process

Check if 2,3,4,5 are all covered

Output

All numbers covered → true

Key Takeaway

🎯 Key Insight: Check if every number in the target range falls within at least one of the given intervals

Asked in

a Amazon 15 G Google 12

The key insight is to check if every number in the target range [left, right] is covered by at least one interval. The brute force approach checks each number against all ranges. The hash set approach pre-marks all covered numbers for O(1) lookup. Best approach depends on range sizes: brute force for small ranges, hash set for large coverage areas. Time: O(n×m), Space: O(1) for brute force.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Smart Coverage Check	O((right - left) × n)	O(1)	Check coverage by iterating through each number and finding if any range covers it efficiently
Brute Force - Check Each Number	O(n × m)	O(1)	Check each number from left to right to see if it's covered by any range
Hash Set - Mark Covered Numbers	O(S + (right - left))	O(S)	Use a hash set to mark all covered numbers, then check if target range is fully covered

Optimized - Smart Coverage Check — Algorithm Steps

Iterate through numbers from left to right
For each number, check if it's within any range's bounds
Return false immediately if any number is uncovered

Visualization

Tap to expand

Step-by-Step Walkthrough

Check 1

Found in [1,10] ✓

Check 22

Not in any range ✗

Early Exit

Return false immediately

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int ranges[][2], int rangesSize, 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;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for ranges
    int ranges[50][2];
    int rangesSize = 0;
    char* ptr = line + 1; // Skip first '['
    while (*ptr && rangesSize < 50) {
        if (*ptr == '[') {
            ptr++;
            ranges[rangesSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr == ',') ptr++;
            ranges[rangesSize][1] = atoi(ptr);
            rangesSize++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    int left, right;
    scanf("%d", &left);
    scanf("%d", &right);
    
    bool result = solution(ranges, rangesSize, left, right);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((right - left) × n)

For each number in target range, check against all n ranges

✓ Linear Growth

Space Complexity

O(1)

Only using variables, no extra data structures needed

✓ Linear Space

35.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Smart Coverage Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler