Skip to main content

Maximum Consecutive Floors Without Special Floors

Problem Statement​

In this tutorial, we will solve the Maximum Consecutive Floors Without Special Floors problem . We will provide the implementation of the solution in Python, Java, and C++.

Problem Description​

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.

Examples​

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 of Given Problem​

Intuition and Approach​

The problem can be solved using a brute force approach or an optimized Technique.

Approach 1:Brute Force (Naive)​

Brute Force Approach: Generate all possible ranges between bottom and top. Check each range to see if it contains any special floors. Track the length of the longest range that does not contain any special floors.

Codes in Different Languages​

Written by @AmruthaPariprolu
#include <vector>
#include <algorithm>

int maxConsecutiveBruteForce(int bottom, int top, std::vector<int>& special) {
int max_consecutive = 0;
for (int start = bottom; start <= top; ++start) {
for (int end = start; end <= top; ++end) {
bool is_special = false;
for (int floor = start; floor <= end; ++floor) {
if (std::find(special.begin(), special.end(), floor) != special.end()) {
is_special = true;
break;
}
}
if (!is_special) {
max_consecutive = std::max(max_consecutive, end - start + 1);
}
}
}
return max_consecutive;
}


Complexity Analysis​

  • Time Complexity: O(n∗m)O(n*m)
  • where n is (top-bottom) , m is len(special) , it generates all possible floor ranges and checks each floor within those ranges against the special floors, resulting in a very high computational cost.
  • Space Complexity: O(1)O(1)
  • It uses a constant amount of extra space regardless of the input size, as it only keeps track of the maximum consecutive floors.

Authors:

Loading...