Jobs

Interviews

Discussions

Check if All the Integers in a Range Are Covered

Easy

Asked by:

4 views

Topics:

Arrays

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.

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 <= 50
1 <= start_i <= end_i <= 50
1 <= left <= right <= 50

Try coding it in LeetCode

Check if All the Integers in a Range Are Covered

Easy

Asked by:

4 views

Topics:

Arrays

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.

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 <= 50
1 <= start_i <= end_i <= 50
1 <= left <= right <= 50

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the intervals in the `ranges` array sorted in any particular order, for example, by their start points?
Can the intervals within the `ranges` array overlap with each other, such as `[[1, 5], [3, 7]]`?
The constraints mention that `left <= right` and all values are positive. What is the expected behavior for an empty `ranges` array?
Just to confirm the constraints, are all numbers involved (`start_i`, `end_i`, `left`, `right`) strictly positive and capped at 50?
If the range `[left, right]` is very large, but completely contained within a single interval in `ranges` (e.g., `ranges = [[1, 100]], left = 10, right = 90`), is that a valid test case to consider?

Brute Force Solution

Approach

The brute force strategy is like using a checklist. We go through every single number we're interested in, from the start to the end of the target range, and for each one, we exhaustively search through all the provided number ranges to see if it's covered.

Here's how the algorithm would work step-by-step:

First, take the starting number of the range you need to verify.
Go through each of the provided number ranges one by one and check if your number falls within any of them.
If your number is not found inside any of the provided ranges after checking all of them, you can stop immediately. The answer is that the range is not fully covered.
If you did find your number in at least one of the ranges, then it's 'covered'. You can then move on to the very next number in the range you need to verify.
Repeat this process for every subsequent number until you reach the end of your target range.
If you are able to check every single number in the target range this way and they are all found to be covered, then the entire range is covered.

Code Implementation

def is_covered_brute_force(ranges, left, right):
    # We must check every integer from left to right to ensure full coverage of the target range.

    for number_to_check in range(left, right + 1):
        is_covered_by_any_interval = False

        # This flag tracks if the current number is found; it must be reset for each new number.

        for current_interval in ranges:
            if current_interval[0] <= number_to_check <= current_interval[1]:
                is_covered_by_any_interval = True
                break

        # If after checking all intervals the number is not covered, the whole range fails immediately.

        if not is_covered_by_any_interval:
            return False

    # If the outer loop completes, every number was covered, so the entire range is covered.

    return True

Big(O) Analysis

Time Complexity

O(K * N) – The time complexity is driven by a nested loop structure. The outer loop iterates through every integer in the target range from 'left' to 'right'. For each of these integers, the inner loop scans through all provided intervals in the 'ranges' array to find if the integer is covered. If we define K as the size of the target range (right - left + 1) and N as the number of intervals, the total operations are approximately K * N, which simplifies to a time complexity of O(K * N).

Space Complexity

O(1) – The space complexity is constant because this approach does not create any new data structures whose size depends on the input. The algorithm only needs a few variables to operate: one to keep track of the current number being checked from the target range, and another to iterate through the provided ranges. The memory required for these variables is fixed and does not grow with the number of input ranges (N) or the length of the target range, resulting in O(1) auxiliary space.

Optimal Solution

Approach

The core idea is to simplify the problem by first combining any overlapping number ranges into larger, continuous segments. Once we have this cleaned-up list of covered segments, we can easily check if we can 'walk' from our required start number to our end number by jumping between these segments without falling into any gaps.

Here's how the algorithm would work step-by-step:

First, organize all the given number ranges by putting them in order based on their starting points.
Next, merge any ranges that overlap or touch. If one range ends at 10 and the next one starts at 8, you can combine them into one larger range that covers the full span of both.
Keep doing this until you have a simplified list of combined ranges that no longer overlap with each other.
Now, think about the target range you need to check. We'll keep track of how much of this target range we've successfully covered, starting from the beginning.
Go through your simplified list of combined ranges. As long as a combined range touches or includes the area you've already covered, use it to extend your coverage as far as possible.
Repeat this, always trying to extend your covered area further using the next available combined range.
If your covered area eventually grows to include the entire target range from its start to its end, then all the numbers are covered. If you get to a point where you can't extend your coverage any further but haven't reached the end of your target, then there must be an uncovered gap.

Code Implementation

def check_if_range_is_covered(list_of_intervals, range_start, range_end):
    # Sorting allows us to process intervals greedily based on their start points.
    list_of_intervals.sort()

    furthest_point_covered = range_start - 1
    interval_list_index = 0

    while furthest_point_covered < range_end:
        max_reach_in_current_step = furthest_point_covered

        # From all reachable intervals, find the one that extends our coverage the farthest.
        while interval_list_index < len(list_of_intervals) and list_of_intervals[interval_list_index][0] <= furthest_point_covered + 1:
            max_reach_in_current_step = max(max_reach_in_current_step, list_of_intervals[interval_list_index][1])
            interval_list_index += 1

        # If we cannot expand our covered zone, it indicates a gap, so the range isn't fully covered.
        if max_reach_in_current_step == furthest_point_covered:
            return False

        furthest_point_covered = max_reach_in_current_step

    return True

Big(O) Analysis

Time Complexity

O(n log n) – The time complexity is dominated by the initial step of sorting the `n` input ranges based on their starting points, which takes O(n log n) time. After sorting, the process of merging overlapping intervals is a single linear scan that takes O(n) time. Similarly, checking if the resulting merged ranges cover the target interval from left to right is another linear scan costing O(n). Therefore, the sorting step is the computational bottleneck, making the overall complexity O(n log n).

Space Complexity

O(N) – The algorithm's space usage is determined by the creation of a new data structure to hold the "simplified list of combined ranges". This new list is necessary to store the result of merging overlapping or touching intervals from the input. In the worst-case scenario, where no input ranges can be merged, this list will grow to a size of N, where N is the number of ranges in the original input. Therefore, the auxiliary memory required grows linearly with the number of input ranges.

Edge Cases

Case	How to Handle
The target range is a single point where left equals right.	The solution must correctly verify if this single integer is covered by any interval.
The starting integer 'left' is not covered by any interval in ranges.	Any correct approach will fail to find a cover for 'left' and must return false.
A gap exists where a number between left and right is not covered, even if left and right themselves are.	The solution must check every integer in the target range to correctly identify such uncovered gaps.
The provided intervals in 'ranges' are unsorted.	A solution should either not rely on sorted order or it must explicitly sort the intervals as a preprocessing step.
Multiple intervals in 'ranges' are heavily overlapping, covering the same numbers.	The logic correctly handles this redundancy by only requiring a number to be covered by at least one interval.
The target range extends beyond the union of all given intervals.	The check for a number greater than the maximum reach of all intervals will fail, resulting in a false return.
The entire target range [left, right] is contained within a single, larger interval from 'ranges'.	This is a simple true case that should be handled correctly by any valid algorithm.
Inputs use the extreme boundary values allowed by the constraints, such as 1 and 50.	The solution must use inclusive checks (<=) to correctly handle numbers on the boundaries of intervals and the target range.

The target range is a single point where left equals right.

How to Handle:

The solution must correctly verify if this single integer is covered by any interval.

The starting integer 'left' is not covered by any interval in ranges.

How to Handle:

Any correct approach will fail to find a cover for 'left' and must return false.

A gap exists where a number between left and right is not covered, even if left and right themselves are.

How to Handle:

The solution must check every integer in the target range to correctly identify such uncovered gaps.

The provided intervals in 'ranges' are unsorted.

How to Handle:

A solution should either not rely on sorted order or it must explicitly sort the intervals as a preprocessing step.

Multiple intervals in 'ranges' are heavily overlapping, covering the same numbers.

How to Handle:

The logic correctly handles this redundancy by only requiring a number to be covered by at least one interval.

The target range extends beyond the union of all given intervals.

How to Handle:

The check for a number greater than the maximum reach of all intervals will fail, resulting in a false return.

The entire target range [left, right] is contained within a single, larger interval from 'ranges'.

How to Handle:

This is a simple true case that should be handled correctly by any valid algorithm.

Inputs use the extreme boundary values allowed by the constraints, such as 1 and 50.

How to Handle:

The solution must use inclusive checks (<=) to correctly handle numbers on the boundaries of intervals and the target range.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the intervals in the `ranges` array sorted in any particular order, for example, by their start points?
Can the intervals within the `ranges` array overlap with each other, such as `[[1, 5], [3, 7]]`?
The constraints mention that `left <= right` and all values are positive. What is the expected behavior for an empty `ranges` array?
Just to confirm the constraints, are all numbers involved (`start_i`, `end_i`, `left`, `right`) strictly positive and capped at 50?
If the range `[left, right]` is very large, but completely contained within a single interval in `ranges` (e.g., `ranges = [[1, 100]], left = 10, right = 90`), is that a valid test case to consider?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, take the starting number of the range you need to verify.
Go through each of the provided number ranges one by one and check if your number falls within any of them.
If your number is not found inside any of the provided ranges after checking all of them, you can stop immediately. The answer is that the range is not fully covered.
If you did find your number in at least one of the ranges, then it's 'covered'. You can then move on to the very next number in the range you need to verify.
Repeat this process for every subsequent number until you reach the end of your target range.
If you are able to check every single number in the target range this way and they are all found to be covered, then the entire range is covered.

Code Implementation

def is_covered_brute_force(ranges, left, right):
    # We must check every integer from left to right to ensure full coverage of the target range.

    for number_to_check in range(left, right + 1):
        is_covered_by_any_interval = False

        # This flag tracks if the current number is found; it must be reset for each new number.

        for current_interval in ranges:
            if current_interval[0] <= number_to_check <= current_interval[1]:
                is_covered_by_any_interval = True
                break

        # If after checking all intervals the number is not covered, the whole range fails immediately.

        if not is_covered_by_any_interval:
            return False

    # If the outer loop completes, every number was covered, so the entire range is covered.

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, organize all the given number ranges by putting them in order based on their starting points.
Next, merge any ranges that overlap or touch. If one range ends at 10 and the next one starts at 8, you can combine them into one larger range that covers the full span of both.
Keep doing this until you have a simplified list of combined ranges that no longer overlap with each other.
Now, think about the target range you need to check. We'll keep track of how much of this target range we've successfully covered, starting from the beginning.
Go through your simplified list of combined ranges. As long as a combined range touches or includes the area you've already covered, use it to extend your coverage as far as possible.
Repeat this, always trying to extend your covered area further using the next available combined range.
If your covered area eventually grows to include the entire target range from its start to its end, then all the numbers are covered. If you get to a point where you can't extend your coverage any further but haven't reached the end of your target, then there must be an uncovered gap.

Code Implementation

def check_if_range_is_covered(list_of_intervals, range_start, range_end):
    # Sorting allows us to process intervals greedily based on their start points.
    list_of_intervals.sort()

    furthest_point_covered = range_start - 1
    interval_list_index = 0

    while furthest_point_covered < range_end:
        max_reach_in_current_step = furthest_point_covered

        # From all reachable intervals, find the one that extends our coverage the farthest.
        while interval_list_index < len(list_of_intervals) and list_of_intervals[interval_list_index][0] <= furthest_point_covered + 1:
            max_reach_in_current_step = max(max_reach_in_current_step, list_of_intervals[interval_list_index][1])
            interval_list_index += 1

        # If we cannot expand our covered zone, it indicates a gap, so the range isn't fully covered.
        if max_reach_in_current_step == furthest_point_covered:
            return False

        furthest_point_covered = max_reach_in_current_step

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
The target range is a single point where left equals right.	The solution must correctly verify if this single integer is covered by any interval.
The starting integer 'left' is not covered by any interval in ranges.	Any correct approach will fail to find a cover for 'left' and must return false.
A gap exists where a number between left and right is not covered, even if left and right themselves are.	The solution must check every integer in the target range to correctly identify such uncovered gaps.
The provided intervals in 'ranges' are unsorted.	A solution should either not rely on sorted order or it must explicitly sort the intervals as a preprocessing step.
Multiple intervals in 'ranges' are heavily overlapping, covering the same numbers.	The logic correctly handles this redundancy by only requiring a number to be covered by at least one interval.
The target range extends beyond the union of all given intervals.	The check for a number greater than the maximum reach of all intervals will fail, resulting in a false return.
The entire target range [left, right] is contained within a single, larger interval from 'ranges'.	This is a simple true case that should be handled correctly by any valid algorithm.
Inputs use the extreme boundary values allowed by the constraints, such as 1 and 50.	The solution must use inclusive checks (<=) to correctly handle numbers on the boundaries of intervals and the target range.

The target range is a single point where left equals right.

How to Handle:

The solution must correctly verify if this single integer is covered by any interval.

The starting integer 'left' is not covered by any interval in ranges.

How to Handle:

Any correct approach will fail to find a cover for 'left' and must return false.

A gap exists where a number between left and right is not covered, even if left and right themselves are.

How to Handle:

The solution must check every integer in the target range to correctly identify such uncovered gaps.

The provided intervals in 'ranges' are unsorted.

How to Handle:

A solution should either not rely on sorted order or it must explicitly sort the intervals as a preprocessing step.

Multiple intervals in 'ranges' are heavily overlapping, covering the same numbers.

How to Handle:

The logic correctly handles this redundancy by only requiring a number to be covered by at least one interval.

The target range extends beyond the union of all given intervals.

How to Handle:

The check for a number greater than the maximum reach of all intervals will fail, resulting in a false return.

The entire target range [left, right] is contained within a single, larger interval from 'ranges'.

How to Handle:

This is a simple true case that should be handled correctly by any valid algorithm.

Inputs use the extreme boundary values allowed by the constraints, such as 1 and 50.

How to Handle:

The solution must use inclusive checks (<=) to correctly handle numbers on the boundaries of intervals and the target range.