{x}
blog image

Maximum Consecutive Floors Without Special Floors

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.

Solution Explanation: Maximum Consecutive Floors Without Special Floors

This problem aims to find the maximum number of consecutive floors without any special floors, given a range of floors and a list of special floors.

Approach:

The most efficient approach involves sorting the special array. After sorting, we can easily identify consecutive gaps between special floors. The maximum consecutive floors without special floors will either be:

  1. The gap between the bottom floor and the first special floor.
  2. The gap between consecutive special floors.
  3. The gap between the last special floor and the top floor.

We calculate these gaps and return the maximum.

Time Complexity Analysis:

  • Sorting the special array takes O(n log n) time, where n is the length of the special array.
  • Iterating through the sorted array to calculate the gaps takes O(n) time.
  • Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity Analysis:

  • The sorting algorithm might use extra space depending on the implementation (e.g., merge sort uses O(n) extra space, while in-place algorithms like quicksort use O(log n) space on average).
  • The space used for storing intermediate variables is constant, O(1).
  • Thus, the overall space complexity is O(n) or O(log n) depending on the sorting algorithm used.

Code Implementation (Python):

from itertools import pairwise
 
class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: list[int]) -> int:
        special.sort()
        max_consecutive = 0
        
        # Gap between bottom and first special floor
        max_consecutive = max(max_consecutive, special[0] - bottom)
 
        # Gaps between consecutive special floors
        for prev, curr in pairwise(special):
            max_consecutive = max(max_consecutive, curr - prev -1)
        
        # Gap between last special floor and top
        max_consecutive = max(max_consecutive, top - special[-1])
 
        return max_consecutive

Code Implementation (Java):

import java.util.Arrays;
 
class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        int maxConsecutive = 0;
 
        // Gap between bottom and first special floor
        maxConsecutive = Math.max(maxConsecutive, special[0] - bottom);
 
        // Gaps between consecutive special floors
        for (int i = 1; i < special.length; i++) {
            maxConsecutive = Math.max(maxConsecutive, special[i] - special[i - 1] - 1);
        }
 
        // Gap between last special floor and top
        maxConsecutive = Math.max(maxConsecutive, top - special[special.length - 1]);
 
        return maxConsecutive;
    }
}

Code Implementation (C++):

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int maxConsecutive(int bottom, int top, std::vector<int>& special) {
        std::sort(special.begin(), special.end());
        int maxConsecutive = 0;
 
        // Gap between bottom and first special floor
        maxConsecutive = std::max(maxConsecutive, special[0] - bottom);
 
        // Gaps between consecutive special floors
        for (size_t i = 1; i < special.size(); ++i) {
            maxConsecutive = std::max(maxConsecutive, special[i] - special[i - 1] - 1);
        }
 
        // Gap between last special floor and top
        maxConsecutive = std::max(maxConsecutive, top - special.back());
 
        return maxConsecutive;
    }
};

Code Implementation (Go):

import "sort"
import "math"
 
func maxConsecutive(bottom int, top int, special []int) int {
	sort.Ints(special)
	maxConsecutive := 0
 
	// Gap between bottom and first special floor
	maxConsecutive = int(math.Max(float64(maxConsecutive), float64(special[0]-bottom)))
 
	// Gaps between consecutive special floors
	for i := 1; i < len(special); i++ {
		maxConsecutive = int(math.Max(float64(maxConsecutive), float64(special[i]-special[i-1]-1)))
	}
 
	// Gap between last special floor and top
	maxConsecutive = int(math.Max(float64(maxConsecutive), float64(top-special[len(special)-1])))
 
	return maxConsecutive
}

Code Implementation (Javascript):

/**
 * @param {number} bottom
 * @param {number} top
 * @param {number[]} special
 * @return {number}
 */
var maxConsecutive = function(bottom, top, special) {
    special.sort((a, b) => a - b);
    let maxConsecutive = 0;
 
    // Gap between bottom and first special floor
    maxConsecutive = Math.max(maxConsecutive, special[0] - bottom);
 
    // Gaps between consecutive special floors
    for (let i = 1; i < special.length; i++) {
        maxConsecutive = Math.max(maxConsecutive, special[i] - special[i - 1] - 1);
    }
 
    // Gap between last special floor and top
    maxConsecutive = Math.max(maxConsecutive, top - special[special.length - 1]);
 
    return maxConsecutive;
};

These code examples all follow the same approach and have the same time and space complexities as explained above. The choice of language depends on your preference and project requirements.