Skip to main content
Talentd

Maximum Consecutive Floors Without Special Floors - Solution & Explanation

MediumArraySorting14 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 105
  • 1 <= bottom <= special[i] <= top <= 109
  • All the values of special are unique.

Approach Overview

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 1: Sorting and Calculating Gaps

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting. Space Complexity: O(1), as sorting is in place.

Try this approach in the editor →

Approach 2: Sliding Window Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where m is the number of special floors. Space Complexity: O(1), constant extra space.

Try this approach in the editor →

Approach 3: 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 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Calculating GapsO(n log n)O(1)General case when the special floors array is unsorted
Sliding Window on Sorted SpecialsO(n log n)O(1)When reasoning about ranges between special floors using two pointers

Video Solution

Maximum Consecutive Floors Without Special Floors | Leetcode 2274 |Two Pointer | Live coding session • Coding Decoded • 779 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximum Consecutive Floors Without Special Floors easy or hard?
The problem is typically rated Medium because it requires recognizing that the answer depends only on gaps between special floors. Once that insight is clear, the implementation becomes straightforward using sorting and a linear scan.
Maximum Consecutive Floors Without Special Floors Python/Java solution
Most implementations follow the same pattern across languages: sort the special array, compute the first boundary gap (special[0] - bottom), scan adjacent pairs using special[i+1] - special[i] - 1, and check the final boundary (top - special[last]). This logic works identically in Python, Java, C++, and JavaScript.
How to solve Maximum Consecutive Floors Without Special Floors in O(n)?
An O(n) scan is possible only if the special floors are already sorted. In that case, iterate once through the array and compute gaps between adjacent floors along with the boundaries from bottom and top. Without a sorted list, sorting is required first, giving O(n log n) complexity overall.
What is the best approach for Maximum Consecutive Floors Without Special Floors?
The most efficient approach is to sort the special floors and compute the gaps between them. After sorting, check the distance from bottom to the first special floor, between adjacent special floors, and from the last special floor to top. The largest gap minus one represents the maximum number of consecutive non‑special floors. This runs in O(n log n) time due to sorting and O(1) extra space.
Is Maximum Consecutive Floors Without Special Floors asked at Google/Amazon/Meta?
Problems involving interval gaps, array sorting, and range scanning are common in interviews at companies like Amazon and Google. While this exact question may vary, the underlying pattern—sorting constraints and finding the largest gap—appears frequently in technical interviews.
What data structure is used in Maximum Consecutive Floors Without Special Floors?
The main data structure used is an array containing the special floors. After sorting the array, the algorithm iterates through it to compute the gaps between consecutive elements and determine the longest valid segment.
What is the time complexity of Maximum Consecutive Floors Without Special Floors?
The optimal solution runs in O(n log n) time where n is the number of special floors. Sorting the array dominates the complexity, and a single linear scan computes the maximum gap. Space complexity is O(1) if the sort is done in place.

Ready to solve this problem?

Practice Maximum Consecutive Floors Without Special Floors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Consecutive Sequence

Next

Maximum Gap