LeetCode Problem 2274

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

LeetCode 2274 - Maximum Consecutive Floors Without Special Floors

Problem Understanding

The problem gives us a range of rented floors in a building, from bottom to top, inclusive. Within this range, some floors are marked as special floors and cannot be counted as regular office floors.

Our task is to determine the largest number of consecutive floors that do not contain any special floor.

For example, suppose Alice rented floors 2 through 9, and the special floors are [4, 6].

The valid non-special ranges become:

• Floors 2 to 3
• Floor 5
• Floors 7 to 9

Among these ranges, the longest consecutive segment contains 3 floors, so the answer is 3.

The important detail is that we are looking for consecutive sequences of floors that avoid every special floor.

The input constraints are large:

• special.length can be up to 10^5
• Floor numbers can be as large as 10^9

These constraints immediately tell us that we cannot iterate through every floor individually when the range is extremely large. Even though the number of special floors is manageable, the total number of floors may not be.

The problem also guarantees:

• Every special floor lies within [bottom, top]
• All special floors are unique

These guarantees simplify the implementation because we do not need to handle duplicates or invalid values.

Several edge cases are important:

• Every rented floor may be special, producing an answer of 0
• There may be long valid ranges before the first special floor
• There may be long valid ranges after the last special floor
• The special array may not be sorted

A naive implementation can easily miss the beginning or ending segments if it only checks gaps between special floors.

Approaches

Brute Force Approach

A straightforward approach is to iterate through every floor from bottom to top and check whether it is special.

We could store all special floors in a hash set for O(1) membership checks. Then we would scan floor by floor, maintaining the current streak of consecutive non-special floors and updating the maximum streak whenever we encounter a special floor.

This approach is correct because it explicitly examines every rented floor and tracks consecutive valid segments directly.

However, it is too slow for the given constraints. The total number of floors can be as large as:

$$10^9$$

Iterating through a billion floors is not feasible.

Optimal Approach

The key observation is that only the positions of the special floors matter.

Instead of checking every floor individually, we can sort the special floors and compute the gaps between them.

Suppose the sorted special floors are:

$$[s_1, s_2, s_3, \dots]$$

Then the valid consecutive ranges are:

• From bottom to s1 - 1
• Between consecutive special floors
• From lastSpecial + 1 to top

The size of a gap between two consecutive special floors a and b is:

$$b - a - 1$$

because both endpoints themselves are special and cannot be included.

By checking all such gaps, we can determine the maximum consecutive sequence efficiently.

Sorting dominates the runtime, making the solution practical for 10^5 elements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(top - bottom + 1)	O(n)	Scans every floor individually
Optimal	O(n log n)	O(1) or O(log n) depending on sorting	Sort special floors and compute gaps

Algorithm Walkthrough

1. Sort the special array in ascending order.

Sorting allows us to process the special floors from left to right and measure the gaps between them correctly. 2. Compute the gap before the first special floor.

The consecutive non-special floors before the first special floor are:

$$special[0] - bottom$$

because the first special floor itself cannot be counted. 3. Initialize the answer with this first gap.

This ensures we correctly handle cases where the longest segment occurs at the beginning. 4. Iterate through adjacent pairs of special floors.

For every pair:

$$special[i - 1], special[i]$$

the number of valid floors between them is:

$$special[i] - special[i - 1] - 1$$

Update the maximum answer if this gap is larger. 5. Compute the gap after the last special floor.

The valid consecutive floors after the last special floor are:

$$top - special[-1]$$ 6. Return the maximum gap found.

Why it works

After sorting, every special floor divides the rented floors into independent intervals. Any valid consecutive segment must lie either:

• Before the first special floor
• Between two consecutive special floors
• After the last special floor

The algorithm checks all three possibilities exactly once. Since every possible valid segment belongs to one of these intervals, the maximum computed gap is guaranteed to be the correct answer.

Python Solution

from typing import List

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.sort()

        max_consecutive = special[0] - bottom

        for i in range(1, len(special)):
            gap = special[i] - special[i - 1] - 1
            max_consecutive = max(max_consecutive, gap)

        max_consecutive = max(max_consecutive, top - special[-1])

        return max_consecutive

The implementation begins by sorting the special floors so that consecutive gaps can be measured correctly.

The variable max_consecutive is initialized using the gap before the first special floor. This handles the possibility that the longest segment starts at bottom.

The loop processes every adjacent pair of special floors. For each pair, we compute the number of floors strictly between them using:

special[i] - special[i - 1] - 1

The subtraction by 1 is necessary because both endpoints are special floors and cannot be included.

Finally, the implementation checks the trailing segment after the last special floor and returns the largest gap encountered.

Go Solution

package main

import "sort"

func maxConsecutive(bottom int, top int, special []int) int {
	sort.Ints(special)

	maxConsecutive := special[0] - bottom

	for i := 1; i < len(special); i++ {
		gap := special[i] - special[i-1] - 1

		if gap > maxConsecutive {
			maxConsecutive = gap
		}
	}

	lastGap := top - special[len(special)-1]

	if lastGap > maxConsecutive {
		maxConsecutive = lastGap
	}

	return maxConsecutive
}

The Go implementation follows the same logic as the Python version.

The primary difference is that Go requires explicit sorting through sort.Ints. Since Go does not provide a built in max function for integers, comparisons are handled manually with if statements.

The constraints guarantee that all values fit comfortably within Go's standard int type.

Worked Examples

Example 1

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

Step 1: Sort special floors

Sorted Special Floors
[4, 6]

Step 2: Gap before first special floor

$$4 - 2 = 2$$

Valid range:

[2, 3]

Variable	Value
max_consecutive	2

Step 3: Process consecutive special floors

For floors 4 and 6:

$$6 - 4 - 1 = 1$$

Valid range:

[5]

Variable	Value
gap	1
max_consecutive	2

Step 4: Gap after last special floor

$$9 - 6 = 3$$

Valid range:

[7, 8, 9]

Variable	Value
last gap	3
max_consecutive	3

Final answer:

3

Example 2

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

Step 1: Sort special floors

Sorted Special Floors
[6, 7, 8]

Step 2: Gap before first special floor

$$6 - 6 = 0$$

Variable	Value
max_consecutive	0

Step 3: Consecutive gaps

Between 6 and 7:

$$7 - 6 - 1 = 0$$

Between 7 and 8:

$$8 - 7 - 1 = 0$$

Variable	Value
max_consecutive	0

Step 4: Gap after last special floor

$$8 - 8 = 0$$

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the special floors dominates the runtime
Space	O(1) or O(log n)	Depends on the sorting implementation

The algorithm processes the special array once after sorting it. The linear scan itself is O(n), but sorting requires O(n log n) time, which becomes the dominant cost.

The extra space usage is minimal because the computation is performed in place after sorting.

Test Cases

from typing import List

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.sort()

        max_consecutive = special[0] - bottom

        for i in range(1, len(special)):
            gap = special[i] - special[i - 1] - 1
            max_consecutive = max(max_consecutive, gap)

        max_consecutive = max(max_consecutive, top - special[-1])

        return max_consecutive

solution = Solution()

assert solution.maxConsecutive(2, 9, [4, 6]) == 3  # provided example
assert solution.maxConsecutive(6, 8, [7, 6, 8]) == 0  # every floor is special

assert solution.maxConsecutive(1, 10, [5]) == 5  # longest segment after special floor
assert solution.maxConsecutive(1, 10, [8]) == 7  # longest segment before special floor

assert solution.maxConsecutive(1, 20, [5, 10, 15]) == 5  # multiple equal gaps

assert solution.maxConsecutive(3, 3, [3]) == 0  # single floor, special

assert solution.maxConsecutive(1, 100, [50]) == 50  # large range split in middle

assert solution.maxConsecutive(10, 20, [11, 12, 13]) == 7  # long suffix segment

assert solution.maxConsecutive(10, 20, [18, 19, 20]) == 8  # long prefix segment

assert solution.maxConsecutive(1, 5, [2, 4]) == 1  # alternating special floors

Test	Why
bottom=2, top=9, [4,6]	Validates standard case
bottom=6, top=8, [7,6,8]	Validates all floors special
bottom=1, top=10, [5]	Longest segment at end
bottom=1, top=10, [8]	Longest segment at beginning
bottom=1, top=20, [5,10,15]	Multiple equal gaps
bottom=3, top=3, [3]	Minimum possible range
bottom=1, top=100, [50]	Large interval split in middle
bottom=10, top=20, [11,12,13]	Large suffix segment
bottom=10, top=20, [18,19,20]	Large prefix segment
bottom=1, top=5, [2,4]	Small alternating gaps

Edge Cases

One important edge case occurs when every rented floor is special. In this scenario, there are no valid non-special floors at all, so the correct answer is 0. A buggy implementation might accidentally return a negative gap or fail to handle zero-length intervals correctly. This implementation handles the case naturally because every computed gap becomes zero.

Another critical edge case occurs when the largest valid segment appears before the first special floor. For example:

bottom = 1
top = 10
special = [8]

The correct answer is 7, corresponding to floors 1 through 7. An implementation that only checks gaps between special floors would miss this entirely. The solution explicitly computes the prefix gap before processing interior gaps.

A similar issue appears when the largest segment occurs after the last special floor. For example:

bottom = 10
top = 20
special = [11, 12]

The longest segment is from 13 to 20. The implementation correctly handles this by computing the suffix gap separately after the loop.

Another subtle edge case involves unsorted input. Since the problem does not guarantee that special is sorted, computing gaps directly without sorting would produce incorrect results. The implementation avoids this issue by sorting the array before any calculations occur.