Maximum Consecutive Floors Without Special Floors

Med

#2072Time: O(N + (top - bottom)), where N is the length of `special`. Populating the `HashSet` takes O(N) time. The main loop runs `top - bottom + 1` times. Since `top` and `bottom` can be up to 10^9, this is too slow for the given constraints.Space: O(N), where N is the number of special floors. This space is used to store the special floors in a `HashSet`.

Algorithms

Sorting

Data structures

Array

Prompt

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.

You are given two integers bottom and top, which denote that Alice has rented all the floors from bottom to top (inclusive). You are also given the integer array special, where special[i] denotes a special floor that Alice has designated for relaxation.

Return the maximum number of consecutive floors without a special floor.

Example 1:

Input: bottom = 2, top = 9, special = [4,6]
Output: 3
Explanation: 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
Explanation: Every floor rented is a special floor, so we return 0.

Constraints:

1 <= special.length <= 10⁵
1 <= bottom <= special[i] <= top <= 10⁹
All the values of special are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This naive approach involves a direct simulation. We iterate through every single floor from bottom to top and keep track of the number of consecutive non-special floors. To quickly check if a floor is special, we first store all special floor numbers in a HashSet.

Algorithm

Create a HashSet from the special array for efficient O(1) average time lookups.
Initialize two variables: maxCount to store the maximum consecutive floors found so far, and currentCount to track the current streak of non-special floors. Both are initialized to 0.
Iterate through every floor f from bottom to top.
For each floor f, check if it is present in the specialFloors set.
If f is a special floor, it means the current streak of non-special floors is broken. Update maxCount = Math.max(maxCount, currentCount) and then reset currentCount to 0.
If f is not a special floor, increment currentCount.
After the loop completes, there might be a final streak of non-special floors that was not terminated by a special floor. Therefore, perform one last comparison: maxCount = Math.max(maxCount, currentCount).
Return maxCount.

Walkthrough

The algorithm works as follows:

Store Special Floors: We put all the elements from the special array into a HashSet. This allows us to check if a floor is special in approximately O(1) time on average.
Iterate and Count: We loop from bottom to top. We use a counter, currentCount, to keep track of the length of the current sequence of non-special floors.
Handle Special Floors: When we encounter a special floor, the sequence is broken. We compare currentCount with our overall maximum, maxCount, update maxCount if necessary, and then reset currentCount to 0.
Handle Non-Special Floors: If the current floor is not special, we simply increment currentCount.
Final Check: After the loop finishes, the last sequence of non-special floors (from the last special floor to top) needs to be accounted for. We do a final comparison between maxCount and currentCount to ensure the last sequence is considered.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int maxConsecutive(int bottom, int top, int[] special) {6        Set<Integer> specialFloors = new HashSet<>();7        for (int s : special) {8            specialFloors.add(s);9        }10 11        int maxCount = 0;12        int currentCount = 0;13        for (int i = bottom; i <= top; i++) {14            if (specialFloors.contains(i)) {15                maxCount = Math.max(maxCount, currentCount);16                currentCount = 0;17            } else {18                currentCount++;19            }20        }21        maxCount = Math.max(maxCount, currentCount);22        return maxCount;23    }24}

Complexity

Time

O(N + (top - bottom)), where N is the length of `special`. Populating the `HashSet` takes O(N) time. The main loop runs `top - bottom + 1` times. Since `top` and `bottom` can be up to 10^9, this is too slow for the given constraints.

Space

O(N), where N is the number of special floors. This space is used to store the special floors in a `HashSet`.

Trade-offs

Pros

Simple to conceptualize and implement.
It is guaranteed to be correct for small input ranges.

Cons

Extremely inefficient for large ranges between bottom and top.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for test cases that adhere to the problem's constraints.

A much more efficient approach is to realize that we don't need to check every floor. The maximum number of consecutive non-special floors can only occur in the 'gaps': either between bottom and the first special floor, between two consecutive special floors, or between the last special floor and top. By sorting the special array, we can easily find the sizes of these gaps in a single pass.

Algorithm

Sort the special array in ascending order.
Calculate the initial gap of non-special floors, which is the range from bottom to the first special floor. This is special[0] - bottom. Initialize max_consecutive with this value.
Iterate through the sorted special array from the second element (i = 1). For each adjacent pair of special floors special[i-1] and special[i], the number of consecutive non-special floors between them is special[i] - special[i-1] - 1. Update max_consecutive with the maximum gap found so far.
After the loop, calculate the final gap, which is the range from the last special floor to top. This is top - special[special.length - 1]. Update max_consecutive one last time.
Return max_consecutive.

Walkthrough

This method avoids iterating through all floors by focusing only on the boundaries defined by bottom, top, and the special floors.

Sort: The first step is to sort the special array. This places the 'dividers' in order, making it easy to calculate the distance between them.
Calculate Initial Gap: The first potential range of consecutive floors is from bottom to the first special floor. The size of this gap is special[0] - bottom.
Calculate Intermediate Gaps: We then iterate through the sorted special array. For any two adjacent special floors, special[i-1] and special[i], the floors between them are all non-special. The number of such floors is special[i] - special[i-1] - 1. We keep track of the maximum gap found.
Calculate Final Gap: The last potential range is from the last special floor to top. The size is top - special[special.length - 1].
Find Maximum: The answer is the maximum of the initial, intermediate, and final gaps.

1import java.util.Arrays;2 3class Solution {4    public int maxConsecutive(int bottom, int top, int[] special) {5        // Sort the special floors to easily find consecutive gaps6        Arrays.sort(special);7 8        int n = special.length;9        // Calculate the initial gap from 'bottom' to the first special floor10        int maxConsecutive = special[0] - bottom;11 12        // Calculate gaps between consecutive special floors13        for (int i = 1; i < n; i++) {14            int gap = special[i] - special[i - 1] - 1;15            maxConsecutive = Math.max(maxConsecutive, gap);16        }17 18        // Calculate the final gap from the last special floor to 'top'19        int lastGap = top - special[n - 1];20        maxConsecutive = Math.max(maxConsecutive, lastGap);21 22        return maxConsecutive;23    }24}

Complexity

Time

O(N log N), where N is the number of special floors. The sorting step dominates the time complexity. The subsequent pass over the sorted array takes O(N) time.

Space

O(log N) to O(N). This is the space complexity for the in-place sort algorithm. For example, Java's `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which requires O(log N) space on average.

Trade-offs

Pros

Highly efficient and optimal for the given constraints.
Avoids iterating through a potentially huge range of floors, making it independent of the top - bottom value.
The logic is clean and directly addresses the core of the problem.

Cons

The approach requires sorting, which modifies the input array special. If the original order must be preserved, a copy of the array should be made first, which would increase the space complexity to O(N).

Solutions

Solution

1class Solution {2public3  int maxConsecutive(int bottom, int top, int[] special) {4    Arrays.sort(special);5    int n = special.length;6    int ans = Math.max(special[0] - bottom, top - special[n - 1]);7    for (int i = 1; i < n; ++i) {8      ans = Math.max(ans, special[i] - special[i - 1] - 1);9    }10    return ans;11  }12}

1class Solution {2public:3  int maxConsecutive(int bottom, int top, vector<int> &special) {4    ranges ::sort(special);5    int ans = max(special[0] - bottom, top - special.back());6    for (int i = 1; i < special.size(); ++i) {7      ans = max(ans, special[i] - special[i - 1] - 1);8    }9    return ans;10  }11};

1class Solution:2    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int: special . sort() ans = max(special[0] - bottom, top - special[- 1]) for i in range(1, len(special)): ans = max(ans, special[i] - special[i - 1] - 1) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem