Maximum Consecutive Floors Without Special Floors — LeetCode 2274 Python Solution

The problem

Alice manages a company and has rented some floors of a building as office space. Alice has decided some of these floors should be special floors, used for relaxation only.

Example

Input

bottom = 2, top = 9, special = [4,6]

Output

3

Explanation

The following are the ranges (inclusive) of consecutive floors without a special floor:

Python solution

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.sort()
        ans = max(special[0] - bottom, top - special[-1])
        for x, y in pairwise(special):
            ans = max(ans, y - x - 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 2274. Maximum Consecutive Floors Without Special Floors 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