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 <= 1051 <= bottom <= special[i] <= top <= 109special are unique.Problem Overview: You are given the lowest floor bottom, the highest floor top, and an array of special floors. A floor is considered valid if it is not special. The task is to find the maximum number of consecutive non‑special floors between bottom and top.
Approach 1: Sorting and Calculating Gaps (O(n log n) time, O(1) extra space)
The key observation: consecutive non‑special floors appear in the gaps between special floors. Sort the special array first using a standard sorting algorithm. Then compute three types of gaps: from bottom to the first special floor, between every pair of adjacent special floors, and from the last special floor to top. For each adjacent pair special[i] and special[i+1], the number of valid floors is special[i+1] - special[i] - 1. Track the maximum gap while iterating through the sorted array. This approach works well because sorting organizes the restricted floors so the largest uninterrupted interval becomes easy to measure.
This solution mainly relies on basic array traversal after sorting. Once sorted, you perform a single linear scan to compute candidate ranges. The logic is simple and deterministic, which makes it a strong choice in interviews when the input list is unsorted.
Approach 2: Sliding Window on Sorted Specials (O(n log n) time, O(1) space)
Another way to reason about the problem is to treat the gap between two special floors as a window of valid floors. After sorting the special array, use a two‑pointer or sliding window technique over adjacent elements. The window boundaries are two special floors, and the size of the valid segment inside the window is right - left - 1. Move the window across the sorted array while updating the maximum gap. You still need to check the boundary windows: bottom → first special and last special → top.
This approach highlights the idea that every maximal segment of non‑special floors is bounded by special floors. The sliding window view is conceptually similar to interval scanning and appears often in problems involving ranges and constraints.
Recommended for interviews: Interviewers expect the sorting + gap calculation solution. It shows you recognized that only the distances between special floors matter. Starting with a brute reasoning about ranges demonstrates understanding, but converting it into a sorted gap scan demonstrates algorithmic maturity using sorting and efficient array iteration.
Sort the special floors and calculate the maximum possible gaps between each pair of consecutive special floors. Don't forget to consider gaps before the first special floor and after the last special floor as well.
This C program sorts the special floors and then iterates through them to find the maximum possible consecutive floors without a special floor. The qsort function is used to sort the special floors array. Gaps are checked before the first special floor, between consecutive special floors, and after the last special floor.
Time Complexity: O(n log n), due to sorting. Space Complexity: O(1), as sorting is in place.
By maintaining a sliding window, you can check each possible subarray of non-special floors and identify the maximum length of such subarrays.
This C program employs a sliding window technique. As it iterates through each floor, it either counts consecutive non-special floors or skips over special ones, updating the maximum count where applicable.
Time Complexity: O(n + m), where m is the number of special floors. Space Complexity: O(1), constant extra space.
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 bottom, as well as the number of floors between the last special floor and top. The maximum of these floor counts is the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array special.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Calculating Gaps | Time Complexity: O(n log n), due to sorting. Space Complexity: O(1), as sorting is in place. |
| Sliding Window Approach | Time Complexity: O(n + m), where m is the number of special floors. Space Complexity: O(1), constant extra space. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Calculating Gaps | O(n log n) | O(1) | General case when the special floors array is unsorted |
| Sliding Window on Sorted Specials | O(n log n) | O(1) | When reasoning about ranges between special floors using two pointers |
Maximum Consecutive Floors Without Special Floors | Leetcode 2274 |Two Pointer | Live coding session • Coding Decoded • 762 views views
Watch 8 more video solutions →Practice Maximum Consecutive Floors Without Special Floors with our built-in code editor and test cases.
Practice on FleetCode