Watch 9 video solutions for Maximum Consecutive Floors Without Special Floors, a medium level problem involving Array, Sorting. This walkthrough by Coding Decoded has 762 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |