Maximum Consecutive Floors Without Special Floors

Medium
853.

Maximum Consecutive Floors Without Special Floors

Maximum Consecutive Floors Without Special Floors is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Microsoft and Freshworks interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} bottom
 * @param {number} top
 * @param {number[]} special
 * @return {number}
 */
var maxConsecutive = function(bottom, top, special) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Consecutive Floors Without Special Floors — Solution

Maximum Consecutive Floors Without Special Floors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Consecutive Floors Without Special Floors is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Microsoft and Freshworks interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy
  • 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.

Hints for Maximum Consecutive Floors Without Special Floors

  1. Hint 1

    Sort the special floors; the free stretches are the gaps between consecutive ones.

  2. Hint 2

    Do not forget the stretch before the first special floor and the one after the last.

  3. Hint 3

    Between special[i-1] and special[i] there are special[i] - special[i-1] - 1 free floors.

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])

Java

public static int maxConsecutive(int bottom, int top, int[] special) {
    int[] s = special.clone();
    Arrays.sort(s);
    int best = s[0] - bottom;
    for (int i = 1; i < s.length; i++) {
        best = Math.max(best, s[i] - s[i - 1] - 1);
    }
    return Math.max(best, top - s[s.length - 1]);
}

C++

int maxConsecutive(int bottom, int top, vector<int>& special) {
    vector<int> s = special;
    sort(s.begin(), s.end());
    int best = s[0] - bottom;
    for (int i = 1; i < (int) s.size(); i++) {
        best = max(best, s[i] - s[i - 1] - 1);
    }
    return max(best, top - s.back());
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms