Leetcode 1040: Moving Stones Until Consecutive II

https://leetcode.com/problems/moving-stones-until-consecutive-ii/description/

On an infinite number line, the position of the i-th stone is given by stones[i].  Call a stone an endpoint stone if it has the smallest or largest position.

Each turn, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone.

In particular, if the stones are at say, stones = [1,2,5], you cannot move the endpoint stone at position 5, since moving it to any position (such as 0, or 3) will still keep that stone as an endpoint stone.

The game ends when you cannot make any more moves, ie. the stones are in consecutive positions.

When the game ends, what is the minimum and maximum number of moves that you could have made?  Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]

Example 1:

Input: [7,4,9]
Output: [1,2]
Explanation: 
We can move 4 -> 8 for one move to finish the game.
Or, we can move 9 -> 5, 4 -> 6 for two moves to finish the game.

Example 2:

Input: [6,5,4,3,10]
Output: [2,3]
We can move 3 -> 8 then 10 -> 7 to finish the game.
Or, we can move 3 -> 7, 4 -> 8, 5 -> 9 to finish the game.
Notice we cannot move 10 -> 2 to finish the game, because that would be an illegal move.

Example 3:

Input: [100,101,104,102,103]
Output: [0,0]

Note:

1. 3 <= stones.length <= 10^4
2. 1 <= stones[i] <= 10^9
3. stones[i] have distinct values.

Notes:

This question is a brain teaser, and not an easy one.

Since we can only start with the smallest one or the largest one, we need to sort the array first.

The maximum moves is relative easier: we can either move the first element to the first available empty position after the second element, or move the last element to the first available empty position before the second last element. After that, we can use the slowest speed to occupy the open spots between the new smallest and largest ones: one by one. And it is easy to calculate the opening positions if we know the lower and upper bounds for a sorted array.

Thus, high = 1 + max(stones[len-1] - stones[1], stones[len-2] - stones[0]) - (n-1).

Now let focus on the lowest number of move.

The final goal is to make it a consecutive array. So we need to find the longest sequence (most number of elements: ct) with the maximum difference of len-1. This can be solved using sliding window method. And the low should be (len - ct).

But there are some special cases: for example, [1, 2, 3, 6] or [1, 4, 5, 6]. Both case gives ct = 3, but low is 2 not 1. In this kind of special cases, we need two steps to make it consecutive.

See the code below:

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        vector<int> res;
        sort(stones.begin(), stones.end());
        int len = stones.size(), ct = 0, left = 0;
        int high = max(stones[len-1] - stones[1], stones[len-2] - stones[0]) - (len - 1) + 1;
        for(int i=0; i<len; ++i) {//the longest sequence with the maximum difference of len-1
            while(stones[i] - stones[left] > len-1) ++left;
            ct = max(ct, i - left + 1);
        }
        int low = len - ct;
        if(low == 1) {//two special cases
            bool f1 = stones[1] - stones[0] > 2 && stones[len-1] - stones[1] == len-2;
            bool f2 = stones[len-1] - stones[len-2] > 2 && stones[len-2] - stones[0] == len-2;
            if(f1 || f2) ++low;
        }
        res.push_back(low);
        res.push_back(high);
        return res;
    }
};