We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Consecutive Floors Without Special Floors

Number: 2355

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a range of floors from bottom to top (inclusive) and a list of special floors within that range, determine the maximum number of consecutive floors that do not include any special floor.

Key Insights

  • Sort the list of special floors.
  • Compute the gap from bottom to the first special floor.
  • Compute gaps between consecutive special floors (subtracting one to exclude the special floors).
  • Compute the gap from the last special floor to the top.
  • The answer is the largest gap computed.

Space and Time Complexity

Time Complexity: O(n log n), due to sorting the special floors array where n is the length of the array. Space Complexity: O(n), used for sorting (depending on implementation) and storing the special floors.

Solution

The algorithm starts by sorting the special floors array. The first potential gap is the distance between the bottom floor and the first special floor. For each pair of consecutive special floors, the gap is their difference minus one, since the special floors themselves are not counted. Finally, the gap from the last special floor to the top floor is considered. The maximum of these values is the answer.

Code Solutions

def max_consecutive(bottom, top, special):
    # Sort the special floors to evaluate consecutive gaps.
    special.sort()
    
    # Initialize the maximum gap as the gap from bottom to the first special floor.
    max_gap = special[0] - bottom
    
    # Compute the gap between consecutive special floors.
    for i in range(1, len(special)):
        # Gap is difference minus 1 because both floors are special.
        current_gap = special[i] - special[i - 1] - 1
        max_gap = max(max_gap, current_gap)
    
    # Consider the gap from the last special floor to top.
    max_gap = max(max_gap, top - special[-1])
    
    return max_gap

# Example usage:
bottom = 2
top = 9
special = [4, 6]
print(max_consecutive(bottom, top, special))  # Expected output: 3
← Back to All Questions