Get started

Maximum Consecutive Floors Without Special Floors — Medium Problem & Solution

You rent every floor from bottom to top inclusive, but the floors listed in special are reserved for others.

  • Difficulty: Medium
  • Topics: Arrays, Greedy, Sorting
  • Asked at: Amazon, Microsoft, Freshworks
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You rent every floor from bottom to top inclusive, but the floors listed in special are reserved for others.

Return the maximum number of consecutive floors you have to yourself.

Example 1

Input: bottom = 2, top = 9, special = [4,6]
Output: 3
Explanation: Floors 7, 8 and 9 are all yours.

Example 2

Input: bottom = 6, top = 8, special = [7,6,8]
Output: 0
Explanation: Every floor is reserved.

Example 3

Input: bottom = 1, top = 10, special = [5]
Output: 5
Explanation: Floors 6 through 10.

Constraints

  • 1 <= special.length <= 100000
  • 1 <= bottom <= special[i] <= top <= 1000000000
  • All values in special are distinct.

How to solve Maximum Consecutive Floors Without Special Floors

Sorting turns the reserved floors into separators. The candidate free stretches are the interval before the first separator, each gap between consecutive separators, and the interval after the last.

Approach

  1. Sort special.
  2. Take special[0] - bottom as the leading stretch.
  3. For each adjacent pair, take special[i] - special[i-1] - 1.
  4. Take top - special[last] as the trailing stretch, and return the maximum.

Why it works

The reserved floors are guaranteed to lie inside [bottom, top], so the free floors are exactly the complement, which is a union of these stretches. The - 1 in the middle gaps excludes both endpoints, while the leading and trailing expressions exclude only one endpoint each — hence their different shape.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Forgetting the edge stretches loses the answer in cases like special = [5].
  • The middle gap needs the - 1; the edge stretches do not.
  • The answer can be 0 when every floor is reserved.

Reference solution

Python

from typing import List

def maxConsecutive(bottom: int, top: int, special: List[int]) -> int:
    s = sorted(special)
    best = s[0] - bottom
    for i in range(1, len(s)):
        best = max(best, s[i] - s[i - 1] - 1)
    return max(best, top - s[-1])

JavaScript

var maxConsecutive = function(bottom, top, special) {
    var s = special.slice().sort(function(a, b) { return a - b; });
    var best = s[0] - bottom;
    for (var i = 1; i < s.length; i++) {
        var gap = s[i] - s[i - 1] - 1;
        if (gap > best) best = gap;
    }
    var tail = top - s[s.length - 1];
    if (tail > best) best = tail;
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue