algoadvance

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

Problem Statement

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

Return true if each integer in the inclusive interval [left, right] is covered by at least one interval in ranges. Otherwise, return false.

Clarifying Questions

  1. Are the elements in ranges always positive integers?
  2. Can the ranges overlap?
  3. Are left and right guaranteed to be within the range defined by elements in ranges?

However, we’ll assume general cases based on the prompt:

  1. ranges can have any integer ranges, including negative.
  2. Yes, ranges can overlap.
  3. No such guarantees; we should handle cases where numbers within [left, right] may not be covered by any interval in ranges.

Strategy

  1. Create a Covered Integer Set:
    • Use an array to mark coverage of integers within the [left, right] range.
    • This array will track which numbers are covered by any of the ranges in ranges.
  2. Mark Coverage:
    • Iterate through each range in ranges.
    • For each range, mark the corresponding elements in the covered array as true.
  3. Check Coverage:
    • After marking, check if all values in the [left, right] range are covered.
    • Return true if all are covered; otherwise, return false.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        vector<bool> covered(right - left + 1, false);
        
        for (const auto& range : ranges) {
            int start = max(left, range[0]);
            int end = min(right, range[1]);
            
            for (int i = start; i <= end; ++i) {
                covered[i - left] = true;
            }
        }
        
        for (bool isCovered : covered) {
            if (!isCovered) return false;
        }
        
        return true;
    }
};

Time Complexity

Thus, the total time complexity is O(m * (right - left + 1)).

This ensures effective handling of checking whether all integers within [left, right] are covered by any of the intervals in ranges.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI