Scale Engineer

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 <= 105
  • 1 <= bottom <= special[i] <= top <= 109
  • 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:

  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.
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;    }}

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.

Solutions

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;  }}

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 →

Next problem