Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2274.html

2274. Maximum Consecutive Floors Without Special Floors

  • Difficulty: Medium.
  • Related Topics: Array, Sorting.
  • Similar Questions: Longest Consecutive Sequence, Maximum Gap.

Problem

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**.

  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 (Java, C++, Python)

  • class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        int start = bottom;
        int ans = 0;
        for (int j : special) {
            if (j - start > ans) {
                ans = j - start;
                start = j + 1;
            } else {
                start = j + 1;
            }
        }
        if (ans < top - special[special.length - 1]) {
            ans = top - special[special.length - 1];
        }
        return ans;
    }
}

############

class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        int n = special.length;
        int ans = Math.max(special[0] - bottom, top - special[n - 1]);
        for (int i = 1; i < n; ++i) {
            ans = Math.max(ans, special[i] - special[i - 1] - 1);
        }
        return ans;
    }
}

  • class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.sort()
        ans = max(special[0] - bottom, top - special[-1])
        for i in range(1, len(special)):
            ans = max(ans, special[i] - special[i - 1] - 1)
        return ans

############

# 2274. Maximum Consecutive Floors Without Special Floors
# https://leetcode.com/problems/maximum-consecutive-floors-without-special-floors/

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.sort()
        res = max(special[0] - bottom, top - special[-1])
        last = special[0] + 1
        
        for x in special[1:]:
            res = max(res, x - last)
            last = x + 1
        
        return res


  • function maxConsecutive(
    bottom: number,
    top: number,
    special: number[],
): number {
    let nums = special.slice().sort((a, b) => a - b);
    nums.unshift(bottom - 1);
    nums.push(top + 1);
    let ans = 0;
    const n = nums.length;
    for (let i = 1; i < n; i++) {
        ans = Math.max(ans, nums[i] - nums[i - 1] - 1);
    }
    return ans;
}

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions