Find Maximal Uncovered Ranges — LeetCode 2655 Python Solution

The problem

You are given an integer n which is the length of a 0-indexed array nums, and a 0-indexed 2D-array ranges, which is a list of sub-ranges of nums (sub-ranges may overlap). Each row ranges[i] has exactly 2 cells: ranges[i][0], which shows the start of the ith range (inclusive) ranges[i][1], which shows the end of the ith range (inclusive) These ranges cover some cells of nums and leave some cells uncovered.

Example

Input

n = 10, ranges = [[3,5],[7,8]]

Output

[[0,2],[6,6],[9,9]]

Explanation

The ranges (3, 5) and (7, 8) are covered, so if we simplify the array nums to a binary array where 0 shows an uncovered cell and 1 shows a covered cell, the array becomes [0,0,0,1,1,1,0,1,1,0] in which we can observe that the ranges (0, 2), (6, 6) and (9, 9) aren't covered.

Python solution

class Solution:
    def findMaximalUncoveredRanges(
        self, n: int, ranges: List[List[int]]
    ) -> List[List[int]]:
        ranges.sort()
        last = -1
        ans = []
        for l, r in ranges:
            if last + 1 < l:
                ans.append([last + 1, l - 1])
            last = max(last, r)
        if last + 1 < n:
            ans.append([last + 1, n - 1])
        return ans

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2655. Find Maximal Uncovered Ranges is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems