1893. Check if All the Integers in a Range Are Covered

EasyArrayHash TablePrefix Sum
Leetcode Link

Problem Description

In the given problem, you are provided with an array called ranges. This array contains subarrays where each subarray [start, end] represents a range of numbers from start to end, including both start and end. In addition to this array, you are given two integers left and right, which define a range of their own. The task is to determine whether every number within the range from left to right (inclusive) is covered by at least one range specified by the subarrays in ranges. If every number in the range [left, right] is found within one or more of the given ranges, you should return true. Otherwise, return false.

An integer is considered covered if it lies within any of the given ranges, inclusive of the range's endpoints. In simpler terms, you need to ensure that there are no gaps in coverage from left to right. If you find even one number in this range not covered by any intervals in ranges, the answer should be false.

Intuition

The idea behind the provided solution is to leverage a technique known as the "difference array". The difference array approach is useful in handling queries of range update operations efficiently and can be used in situations like this, where we have to add or subtract values over a range and then check the sum or coverage over a continuous range.

Here, we create an auxiliary array called diff with extra elements (up to 52, taking into account possible values from left and right). Initially, this diff array is filled with zeros. The intuition is to increase the value at the start of a range by 1 and decrease the value right after the end of a range by 1. When we traverse through the diff array and compute the prefix sum at each point, we can determine the total coverage at that point. The prefix sum gives us an understanding of how many ranges cover a particular number.

If we follow through with calculating the prefix sums of the diff array, we would find that for any interval [l, r] in ranges, the coverage would be reflected correctly. Once we've processed all the ranges, we'll iterate through the diff array once more. While iterating, if we encounter any place within our [left, right] range where the cumulative coverage drops to 0 (which means it's not covered by any interval), then we immediately return false. If we make it through the entire left to right range and all points are covered, we return true.

The strength of this approach lies in efficiently updating the range coverage and then quickly assessing whether any point within the target range [left, right] is uncovered.

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Solution Approach

The solution to this problem makes use of a simple but powerful concept called the difference array approach, which is particularly useful in scenarios involving increment and decrement operations over a range of elements.

To understand the implementation, we follow these steps:

  1. We initialize a difference array diff with a length sufficient to cover all possible values in the problem statement. Here, we fixed its length to 52, which is an arbitrary choice to ensure that we can accommodate all ranges given that actual range requirements are not specified. This diff array tracks the net change at each point.

  2. We iterate over the given ranges array. For each range [l, r], we increment diff[l] by 1 and decrement diff[r + 1] by 1. The increment at diff[l] indicates that at point l, the coverage starts (or increases), and the decrement at diff[r + 1] indicates that right after point r, the coverage ends (or decreases).

  3. We then iterate over diff and compute the prefix sum at each point. We use a variable cur to keep track of the cumulative sum as we go.

    • The prefix sum up to a certain index i in the diff array essentially represents the number of ranges covering the point corresponding to i.

  4. During the same iteration, we check each position i against our target coverage range [left, right]. If the prefix sum at i (i.e., cur) is 0 for any i within this interval, it means that point i is not covered by any range. Hence, we return false.

  5. If we successfully iterate over the entire [left, right] interval without finding any points with 0 coverage, we return true, since this implies that all points within the target range are covered by at least one interval in ranges.

The key algorithmic concepts used in the implementation are iteration, conditional checks, and the management of prefix sums, which allow us to track the cumulative effect of all the ranges on any given point.

This approach is efficient because each range update (increment and decrement at the start and end points of the range) is performed in constant time, and the final check for uncovered points is performed in a single pass through the diff array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Assume we have an array ranges given as [[1, 2], [5, 6], [1, 5]], and we need to check if all numbers in the range [1, 6] are covered by at least one of the intervals in ranges.

Following the steps outlined in the solution approach:

Step 0 (Initial Setup):

  • We define left = 1, right = 6, and we initialize our diff array of size 52 (to cover the possible range) with all 0s.

Step 1 (Updating the Difference Array):

  • For the range [1, 2], we increment diff[1] by 1 and decrement diff[3] by 1.
  • For the range [5, 6], we increment diff[5] by 1 and decrement diff[7] by 1.
  • For the range [1, 5], we increment diff[1] again by 1 and decrement diff[6] by 1.

After step 1, the starting segment of our diff array looks like this: [0, 2, 0, -1, 0, 1, -2, 1, ... (remaining all zeros)].

Step 2 (Computing Prefix Sums and Checking for Coverage):

  • We initialize cur to 0 and start iterating from 1 to 6 (the range [left, right]). We will compute the prefix sum and check it against our coverage requirement:
    • At i = 1: cur += diff[1] (which is 2), so cur becomes 2.
    • At i = 2: cur += diff[2] (which is 0), so cur remains 2.
    • At i = 3: cur += diff[3] (which is -1), so cur becomes 1.
    • At i = 4: cur += diff[4] (which is 0), so cur remains 1.
    • At i = 5: cur += diff[5] (which is 1), so cur becomes 2.
    • At i = 6: cur += diff[6] (which is -2), so cur becomes 0.

During this iteration, we check whether cur becomes 0 before reaching the end of our range. Here, cur does become 0 at i = 6, indicating that the point 6 is not covered by any interval since the cumulative sum drops to zero at this point.

Thus according to our algorithm, we would return false, as there is at least one number (6) in the range [left, right] that isn't covered by any range in ranges.

Through this small example, we've followed the difference array approach to determine whether every number within the target range is covered by the given ranges. By performing constant time updates to our diff array and a single pass check, we efficiently arrive at our answer.

Solution Implementation

1class Solution:
2    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
3        # Initialize a difference array with 52 elements, one extra to accommodate the 0-indexing and one more to handle the 'r+1' without index error.
4        difference_array = [0] * 52 
5      
6        # Iterate over each range in the ranges list.
7        for range_start, range_end in ranges:
8            # Increment the count at the start index of the range.
9            difference_array[range_start] += 1
10            # Decrement the count immediately after the end index of the range.
11            difference_array[range_end + 1] -= 1
12      
13        # Accumulate the frequency count while traversing from start to end.
14        current_coverage = 0
15        for index, freq_change in enumerate(difference_array):
16            # Update the coverage by adding the current frequency change.
17            current_coverage += freq_change
18          
19            # If the index is in the query range [left, right] and the current coverage is 0,
20            # it means this number is not covered by any range, thus return False.
21            if left <= index <= right and current_coverage == 0:
22                return False
23      
24        # If the loop completed without returning False, all numbers in [left, right] are covered.
25        return True
26
1class Solution {
2    // Method to check if all integers in the range [left, right] are covered by any of the ranges
3    public boolean isCovered(int[][] ranges, int left, int right) {
4        // Array for the difference between the count of start and end points
5        int[] diff = new int[52]; // A size of 52 to cover range from 0 to 50 and to account for the end offset.
6      
7        // Loop through each range in the input array and update the diff array.
8        for (int[] range : ranges) {
9            int start = range[0]; // Start of the current range
10            int end = range[1];   // End of the current range
11          
12            ++diff[start]; // Increment the start index to indicate the range starts here
13            --diff[end + 1]; // Decrement the index after the end point to indicate the range ends before this index
14        }
15      
16        // Variable to keep track of the current coverage status
17        int coverage = 0;
18        // Loop over the diff array and check if all numbers are covered
19        for (int i = 0; i < diff.length; ++i) {
20            coverage += diff[i]; // Add the difference to get the current number of ranges covering i
21          
22            // If the current number falls within the query range and is not covered by any range, return false.
23            if (i >= left && i <= right && coverage == 0) {
24                return false;
25            }
26        }
27      
28        // If we pass through the loop without returning false, all numbers in [left, right] are covered.
29        return true;
30    }
31}
32
1class Solution {
2public:
3    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
4        // Creating a difference array with an extra space to avoid index out-of-bounds,
5        // since we will operate in the range of [1, 50] according to the problem's constraints
6        int diff[52] = {};
7
8        // Iterate through each range and maintain a difference array
9        for (auto& range : ranges) {
10            int rangeStart = range[0];
11            int rangeEnd = range[1];
12            // Increment at the start index, indicating the beginning of a range covering
13            ++diff[rangeStart];
14            // Decrement just after the end index, indicating the end of coverage
15            --diff[rangeEnd + 1];
16        }
17
18        // Initialize a variable to track the coverage at each point
19        int coverage = 0;
20
21        // Iterate through the hypothetical line where the points need to be covered
22        for (int i = 1; i < 52; ++i) {
23            // Apply the effect of the current index on the coverage
24            coverage += diff[i];
25            // Check if the current index falls within the range to be checked for coverage
26            if (i >= left && i <= right) {
27                // If the coverage drops to zero or below, it means this point is not covered
28                if (coverage <= 0) {
29                    return false;
30                }
31            }
32        }
33
34        // If the function hasn't returned false, all points are covered
35        return true;
36    }
37};
38
1function isCovered(ranges: number[][], left: number, right: number): boolean {
2    // Create a difference array with an initially filled with zeros to track coverages.
3    const coverageDiff = new Array(52).fill(0);
4
5    // Populate the difference array using the range updates (using the prefix sum technique).
6    for (const [start, end] of ranges) {
7        ++coverageDiff[start];
8        --coverageDiff[end + 1];
9    }
10
11    // 'currentCoverage' will track the coverage of the current position by summing up values.
12    let currentCoverage = 0;
13
14    // Iterate through each position up to 51 (given the array starts at 0).
15    for (let position = 0; position < 52; ++position) {
16        // Add the coverage difference at the current position to the running total 'currentCoverage'.
17        currentCoverage += coverageDiff[position];
18
19        // If the current position is within the specified range and is not covered, return false.
20        if (position >= left && position <= right && currentCoverage <= 0) {
21            return false;
22        }
23    }
24
25    // If all positions in the specified range are covered, return true.
26    return true;
27}
28
Not Sure What to Study? Take the 2-min Quiz：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Time and Space Complexity

The given Python code implements a difference array to determine if all the numbers in the interval [left, right] are covered by at least one of the ranges in ranges.

Time complexity:

The time complexity of this algorithm is determined by several steps in the code:

  1. Initialize the difference array: The difference array diff has a fixed size of 52, so this step is O(1).

  2. Populate the difference array: For each range [l, r] in ranges, we perform a constant time operation to increment and decrement at position l and r + 1, respectively. If there are n ranges in ranges, this step has a complexity of O(n).

  3. Accumulate the difference array and check coverage: We then accumulate the difference array values to get the coverage count up to each index. Since the range of the diff array is from 0 to 51, this step is O(52) which is O(1) as it has a fixed size.

  4. Checking the interval [left, right]: We iterate through the diff array, which is a fixed size, and checking if the coverage is 0 for any point between [left, right]. This is also O(1) since the interval [left, right] is within a fixed-size range.

    The final time complexity is the sum of the complexities of these steps: O(n) + O(1) + O(1) + O(1), which simplifies to O(n) where n is the number of ranges provided.

Space complexity:

The space complexity is determined by the storage used which is mainly for the difference array:

  1. Difference array diff: A fixed-size array of length 52 is used, so space complexity is O(1), as it doesn't depend on the input size.

Therefore, the overall space complexity of the algorithm is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫