#2274

Medium

LeetCode Problem Workspace

Maximum Consecutive Floors Without Special Floors

Find the maximum sequence of consecutive floors without any special floors using array sorting techniques efficiently.

Problem Statement

Alice manages a building and has rented floors numbered from bottom to top inclusive. She has marked certain floors as special for relaxation, which cannot be counted in consecutive sequences.

Given two integers bottom and top and an array special representing special floors, return the maximum number of consecutive floors that do not include any special floor. Consider that gaps between sorted special floors define the consecutive sequences.

Examples

Example 1

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

Output: 3

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

(2, 3) with a total amount of 2 floors.
(5, 5) with a total amount of 1 floor.
(7, 9) with a total amount of 3 floors. Therefore, we return the maximum number which is 3 floors.

Example 2

Input: bottom = 6, top = 8, special = [7,6,8]

Output: 0

Every floor rented is a special floor, so we return 0.

Constraints

1 <= special.length <= 105
1 <= bottom <= special[i] <= top <= 109
All the values of special are unique.

Solution Approach

Sort Special Floors

Sorting the special floors array ensures we can analyze consecutive gaps efficiently. Once sorted, differences between adjacent special floors minus one give the counts of consecutive non-special floors.

Compute Floor Gaps

Iterate from bottom to the first special floor and between each pair of special floors. The gap calculation x - y - 1 between two consecutive special floors captures all consecutive floors without a special floor.

Track Maximum

Maintain a variable to store the maximum consecutive count while checking all gaps. Include the final gap between the last special floor and top floor to ensure the largest sequence is found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the special floors array takes O(n log n) time where n is the number of special floors. Iterating through the sorted array to compute gaps is O(n). Space complexity is O(1) if sorting in place, otherwise O(n) for storing a sorted copy.

What Interviewers Usually Probe

Sorting special floors is critical for correct gap calculation.
Checking all edge cases including first and last floor gaps is expected.
Tracking maximum while iterating shows understanding of array manipulation patterns.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort special floors before computing gaps leads to incorrect results.
Ignoring the gap before the first special floor or after the last special floor can miss the true maximum.
Assuming consecutive floors are only between special floors and not including bottom and top boundaries.

Follow-up variants

Return both the maximum consecutive floors and the starting floor of that sequence.
Count the total number of consecutive sequences longer than a given threshold.
Allow dynamic insertion of special floors and compute the maximum consecutive floors after each insertion.

FAQ

How does sorting special floors help in finding maximum consecutive floors?

Sorting ensures that we can calculate gaps between consecutive special floors accurately, which directly gives consecutive non-special floors.

What if all floors are special?

If all floors between bottom and top are special, there are no consecutive non-special floors, so the result is 0.

How is the gap between special floors calculated?

For two sorted special floors x and y, the number of consecutive non-special floors is x - y - 1.

Does the bottom or top floor affect the result?

Yes, gaps before the first special floor and after the last special floor must be considered to find the true maximum.

What pattern does this problem follow in arrays?

This is an array plus sorting pattern problem where sorting enables efficient consecutive gap computation between special elements.

terminal

Solution

Solution 1: Sorting

We can sort the special floors in ascending order, then calculate the number of floors between each pair of adjacent special floors. Finally, we calculate the number of floors between the first special floor and $\textit{bottom}$, as well as the number of floors between the last special floor and $\textit{top}$. The maximum of these floor counts is the answer.

1

2

3

4

5

6

7

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

Continue Practicing

#2273 find resultant array after removing anagrams #2271 maximum white tiles covered by a carpet #2279 maximum bags with full capacity of rocks