Hex.*

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

Posted on In
Leetcode: 135/2658 (57+64+14)

Description

You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [starti, endi] represents an inclusive interval between starti and endi.
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] = [starti, endi] if starti <= x <= endi.

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 <= starti <= endi <= 50
1 <= left <= right <= 50

Solutions

Brute Force

Store all the numbers that appear in ranges in the set of nums, and then traverse the range from left to right, if the numbers are all in nums, return True, if there are numbers that are not included, return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# O(n) time | O(n) space
class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        nums = set()
        for start, end in ranges:
            for i in range(start, end+1):
                if i not in nums:
                    nums.add(i)

        for i in range(left, right+1):
            if i not in nums:
                return False
                    
        return True

optimized version

1
2
3
4
5
6
7
8
9
10
11
12
# O(n) time | O(1) space
class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        for i in range(left, right+1):
            flag = 0
            for start, end in ranges:
                if start <= i <= end:
                    flag = 1
            if flag == 0:
                return False

        return True

Difference Array

Traverse ranges, starting from ranges[0] to calculate the covered changes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# O(n) time | O(n) time
class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        diff = [0] * 52
        # get difference array
        for start, end in ranges:
            diff[start] += 1
            diff[end+1] -=1

        # prefix sum
        for i in range(1, 52):
            diff[i] += diff[i-1]

        for i in range(left, right+1):
            if diff[i] == 0:
                return False
        return True

# 执行用时：24 ms, 在所有 Python3 提交中击败了98.94%的用户
# 内存消耗：14.7 MB, 在所有 Python3 提交中击败了99.29%的用户