Skip to content

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

Approach 1: Naive

  • Time: $O(nk)$, where k = right - left + 1
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  bool isCovered(vector<vector<int>>& ranges, int left, int right) {
    for (int i = left; i <= right; ++i) {
      bool seen = false;
      for (const vector<int>& range : ranges)
        if (i >= range[0] && i <= range[1]) {
          seen = true;
          break;
        }
      if (!seen)
        return false;
    }

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public boolean isCovered(int[][] ranges, int left, int right) {
    for (int i = left; i <= right; ++i) {
      boolean seen = false;
      for (int[] range : ranges)
        if (i >= range[0] && i <= range[1]) {
          seen = true;
          break;
        }
      if (!seen)
        return false;
    }

    return true;
  }
}

1
2
3
4
class Solution:
  def isCovered(self, ranges: list[list[int]], left: int, right: int) -> bool:
    return all(any(l <= i <= r for l, r in ranges) for i in range(
        left, right + 1))

Approach 2: Line Sweep

  • Time: $O(n + k)$, where k = right - left + 1
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  bool isCovered(vector<vector<int>>& ranges, int left, int right) {
    vector<int> seen(52);

    for (const vector<int>& range : ranges) {
      ++seen[range[0]];
      --seen[range[1] + 1];
    }

    for (int i = 1; i < 52; ++i)
      seen[i] += seen[i - 1];

    for (int i = left; i <= right; ++i)
      if (!seen[i])
        return false;

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public boolean isCovered(int[][] ranges, int left, int right) {
    int[] seen = new int[52];

    for (int[] range : ranges) {
      ++seen[range[0]];
      --seen[range[1] + 1];
    }

    for (int i = 1; i < 52; ++i)
      seen[i] += seen[i - 1];

    for (int i = left; i <= right; ++i)
      if (seen[i] == 0)
        return false;

    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def isCovered(self, ranges: list[list[int]], left: int, right: int) -> bool:
    seen = [0] * 52

    for l, r in ranges:
      seen[l] += 1
      seen[r + 1] -= 1

    for i in range(1, 52):
      seen[i] += seen[i - 1]

    return all(seen[i] for i in range(left, right + 1))