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.

• Brute Force
• Optimized approach

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

C++

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

Java

Written by @AmruthaPariprolu

import java.util.*;

public class MaxConsecutiveBruteForce {
    public int maxConsecutive(int bottom, int top, int[] special) {
        int max_consecutive = 0;
        for (int start = bottom; start <= top; ++start) {
            for (int end = start; end <= top; ++end) {
                boolean is_special = false;
                for (int floor = start; floor <= end; ++floor) {
                    if (Arrays.binarySearch(special, floor) >= 0) {
                        is_special = true;
                        break;
                    }
                }
                if (!is_special) {
                    max_consecutive = Math.max(max_consecutive, end - start + 1);
                }
            }
        }
        return max_consecutive;
    }
}

Python

Written by @AmruthaPariprolu

def max_consecutive_brute_force(bottom, top, special):
    max_consecutive = 0
    for start in range(bottom, top + 1):
        for end in range(start, top + 1):
            is_special = False
            for floor in range(start, end + 1):
                if floor in special:
                    is_special = True
                    break
            if not is_special:
                max_consecutive = max(max_consecutive, end - start + 1)
    return max_consecutive

Complexity Analysis

• Time Complexity: $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)$
• 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...