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 <= 1000001 <= bottom <= special[i] <= top <= 1000000000All values in special are distinct.
Hints for Maximum Consecutive Floors Without Special Floors
Hint 1
Sort the special floors; the free stretches are the gaps between consecutive ones.
Hint 2
Do not forget the stretch before the first special floor and the one after the last.
Hint 3
Between
special[i-1]andspecial[i]there arespecial[i] - special[i-1] - 1free 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
- Sort
special. - Take
special[0] - bottomas the leading stretch. - For each adjacent pair, take
special[i] - special[i-1] - 1. - 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