# Maximum Consecutive Floors Without Special Floors
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-consecutive-floors-without-special-floors)
Canonical: https://scaleengineer.com/dsa/problems/maximum-consecutive-floors-without-special-floors
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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**.

# Approaches
## Brute Force by Iterating All Floors
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`.
**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`.
**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.
### Explanation
The algorithm works as follows:

1.  **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.
2.  **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. 
3.  **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.
4.  **Handle Non-Special Floors**: If the current floor is not special, we simply increment `currentCount`.
5.  **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.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        Set<Integer> specialFloors = new HashSet<>();
        for (int s : special) {
            specialFloors.add(s);
        }

        int maxCount = 0;
        int currentCount = 0;
        for (int i = bottom; i <= top; i++) {
            if (specialFloors.contains(i)) {
                maxCount = Math.max(maxCount, currentCount);
                currentCount = 0;
            } else {
                currentCount++;
            }
        }
        maxCount = Math.max(maxCount, currentCount);
        return maxCount;
    }
}
```
### 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`.

## Efficient Approach by Sorting
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.
**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.
**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).
### Explanation
This method avoids iterating through all floors by focusing only on the boundaries defined by `bottom`, `top`, and the `special` floors.

1.  **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.
2.  **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`.
3.  **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.
4.  **Calculate Final Gap**: The last potential range is from the last special floor to `top`. The size is `top - special[special.length - 1]`.
5.  **Find Maximum**: The answer is the maximum of the initial, intermediate, and final gaps.

```java
import java.util.Arrays;

class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        // Sort the special floors to easily find consecutive gaps
        Arrays.sort(special);

        int n = special.length;
        // Calculate the initial gap from 'bottom' to the first special floor
        int maxConsecutive = special[0] - bottom;

        // Calculate gaps between consecutive special floors
        for (int i = 1; i < n; i++) {
            int gap = special[i] - special[i - 1] - 1;
            maxConsecutive = Math.max(maxConsecutive, gap);
        }

        // Calculate the final gap from the last special floor to 'top'
        int lastGap = top - special[n - 1];
        maxConsecutive = Math.max(maxConsecutive, lastGap);

        return maxConsecutive;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int maxConsecutive(int bottom, int top, int[] special) {
    Arrays.sort(special);
    int n = special.length;
    int ans = Math.max(special[0] - bottom, top - special[n - 1]);
    for (int i = 1; i < n; ++i) {
      ans = Math.max(ans, special[i] - special[i - 1] - 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxConsecutive(int bottom, int top, vector<int> &special) {
    ranges ::sort(special);
    int ans = max(special[0] - bottom, top - special.back());
    for (int i = 1; i < special.size(); ++i) {
      ans = max(ans, special[i] - special[i - 1] - 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```