Leetcode 2274: Maximum Consecutive Floors Without Special Floors

Input: You are given two integers, `bottom` and `top`, representing the range of floors rented. You are also given an integer array `special` where each element represents a special floor within this range.

Example: Input: bottom = 3, top = 10, special = [4, 5, 8]

Constraints:

• 1 <= special.length <= 10^5

• 1 <= bottom <= special[i] <= top <= 10^9

• All the values in the special array are unique.

Output: Return the maximum number of consecutive floors that do not have a special floor.

Example: Output: 3

Constraints:

Goal: Find the longest stretch of consecutive floors without any special floor in the given range.

Steps:

• Sort the special floors in ascending order.

• Track the difference between each adjacent pair of special floors and find the maximum gap.

• Include the gap before the first special floor and after the last special floor.

• Return the maximum gap.

Goal: Ensure that the solution works efficiently within the given constraints.

Steps:

• The solution should efficiently handle large inputs, including up to 100,000 special floors.

Assumptions:

• The special floors are within the range from `bottom` to `top`.

• There are no repeated special floors in the input array.

• Input: Input: bottom = 3, top = 10, special = [4, 5, 8]

• Explanation: The special floors are 4, 5, and 8. The largest gap is between 7 and 10, which contains 3 consecutive floors. Therefore, the result is 3.

• Input: Input: bottom = 6, top = 8, special = [6, 7, 8]

• Explanation: All floors are special, so there are no consecutive floors without a special floor. The result is 0.

Approach: To solve this problem, we first sort the special floors and then calculate the gaps between consecutive special floors, including the initial gap and the final gap. The largest of these gaps will be the maximum number of consecutive non-special floors.

Observations:

• Sorting the special floors helps easily identify the gaps between them.

• We can treat the gap before the first special floor and after the last special floor as part of the solution.

• The problem can be solved by calculating the gaps between adjacent special floors and finding the largest gap. This involves sorting and a linear scan.

Steps:

• Sort the array `special`.

• Initialize `prv` as `bottom - 1` and calculate the gaps between consecutive special floors.

• For each special floor, calculate the gap between it and the previous special floor and update the result.

• After processing all special floors, calculate the final gap from the last special floor to `top`.

Empty Inputs:

• The special array will not be empty, but ensure that `bottom` and `top` are valid inputs.

Large Inputs:

• For large inputs with up to 100,000 special floors, the solution should handle sorting efficiently.

Special Values:

• If the special floors are at the start or end of the range, handle the gaps before and after properly.

Constraints:

• The solution should work efficiently even when the range between `bottom` and `top` is very large (up to 10^9).

int maxConsecutive(int bottom, int top, vector<int>& spec) {

    sort(spec.begin(), spec.end());
    int prv = bottom - 1, n = spec.size();

    int res = 0;
    for(int cur : spec) {
        res = max(res, cur - prv - 1);
        prv = cur > prv ? cur : prv;
    }
    res = max(res, top - prv);

    return res;
}
};

// bottom - top
// spec

1 : Function Declaration

int maxConsecutive(int bottom, int top, vector<int>& spec) {

This is the function header for `maxConsecutive`, which calculates the largest gap between consecutive numbers in a specified range that are missing from the array `spec`.

2 : Sorting

    sort(spec.begin(), spec.end());

Sorts the vector `spec` in ascending order to make it easier to identify gaps between consecutive integers.

3 : Variable Initialization

    int prv = bottom - 1, n = spec.size();

Initializes `prv` to `bottom - 1` (a marker for the last considered integer before `bottom`) and `n` to the size of the `spec` vector.

4 : Variable Initialization

    int res = 0;

Initializes `res` to 0, which will store the maximum gap between consecutive integers.

5 : Loop Start

    for(int cur : spec) {

Starts a for-each loop to iterate through each element `cur` in the sorted `spec` vector.

6 : Gap Calculation

        res = max(res, cur - prv - 1);

Calculates the gap between the current number `cur` and the previous number `prv`, and updates `res` if this gap is larger than the previous maximum gap.

7 : Update Previous Value

        prv = cur > prv ? cur : prv;

Updates `prv` to the maximum of `prv` and `cur` to ensure that `prv` always holds the most recent number considered.

8 : Final Gap Calculation

    res = max(res, top - prv);

After the loop, calculates the gap between the last element `prv` and the `top` value, and updates `res` if this final gap is larger than the previous maximum.

9 : Return Statement

    return res;

Returns the value of `res`, which represents the maximum consecutive gap between numbers that are missing in the range [bottom, top].

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The worst-case time complexity is O(n log n), where n is the number of special floors, due to the sorting step.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the storage required for the special floors array.

Leetcode 2274: Maximum Consecutive Floors Without Special Floors

Explore →