# Moving Stones Until Consecutive II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/moving-stones-until-consecutive-ii)
Canonical: https://scaleengineer.com/dsa/problems/moving-stones-until-consecutive-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
There are some stones in different positions on the X-axis. You are given an integer array `stones`, the positions of the stones.

Call a stone an **endpoint stone** if it has the smallest or largest position. In one move, 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 (i.e., the stones are in three consecutive positions).

Return _an integer array_ `answer` _of length_ `2` _where_:

* `answer[0]` _is the minimum number of moves you can play, and_
* `answer[1]` _is the maximum number of moves you can play_.

**Example 1:**

**Input:** stones = [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:** stones = [6,5,4,3,10]
**Output:** [2,3]
**Explanation:** 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.

**Constraints:**

* `3 <= stones.length <= 104`
* `1 <= stones[i] <= 109`
* All the values of `stones` are **unique**.

# Approaches
## Sorting and Brute-Force Window Search
This approach first sorts the array to easily identify endpoints and analyze stone distributions. The maximum number of moves can be calculated with a simple formula based on the span of stones, excluding one of the endpoints. For the minimum moves, we adopt a brute-force strategy. We check every possible window of size `n` that could contain the final consecutive sequence of stones. For each stone `stones[i]`, we form a window `[stones[i], stones[i] + n - 1]` and count how many of the original stones fall into it. The maximum count found, `max_k`, tells us the minimum number of stones we need to move is `n - max_k`. A special case where `n-1` stones are consecutive but separated from the last stone requires 2 moves, which must be handled separately.
**Time:** O(N^2), dominated by the nested loops for calculating the minimum moves. Sorting takes O(N log N), which is less significant. · **Space:** O(N) or O(log N), depending on the implementation of the sorting algorithm. If an in-place sort is used, it's O(log N) for recursion stack. If a copy is made, it's O(N).
**Pros:** The logic is relatively straightforward to understand, especially the brute-force part for minimum moves.; It correctly calculates the maximum moves in constant time after sorting.
**Cons:** The `O(N^2)` complexity for finding the minimum moves can be too slow for large inputs, potentially leading to a 'Time Limit Exceeded' error on some platforms.
### Explanation
First, we sort the `stones` array. Let `n` be the number of stones.

**Maximum Moves (`max_moves`)**
The maximum number of moves is achieved by consolidating stones from one end while leaving the other end as spread out as possible. This corresponds to the number of empty slots in either the range `[stones[0], stones[n-2]]` or `[stones[1], stones[n-1]]`. The number of moves will be the maximum of these two scenarios.
- Moves to make `stones[0], ..., stones[n-2]` consecutive: `stones[n-2] - stones[0] + 1 - (n-1) = stones[n-2] - stones[0] - n + 2`.
- Moves to make `stones[1], ..., stones[n-1]` consecutive: `stones[n-1] - stones[1] + 1 - (n-1) = stones[n-1] - stones[1] - n + 2`.
So, `max_moves = max(stones[n-2] - stones[0] - n + 2, stones[n-1] - stones[1] - n + 2)`.

**Minimum Moves (`min_moves`)**
To find the minimum moves, we search for a window of length `n` that covers the most stones. We can iterate through each stone `stones[i]` and consider it the start of a potential final consecutive block. The target window would be `[stones[i], stones[i] + n - 1]`. We then count how many stones are in this window using a nested loop. The maximum count `max_k` gives a base for `min_moves` as `n - max_k`. We must also check a special case where `min_moves` is 2, which occurs when `n-1` stones are consecutive but the last stone is separated by a gap, making it impossible to finish in one move.

```java
import java.util.Arrays;

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;

        // Calculate maximum moves
        int maxMoves = Math.max(stones[n - 1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2);

        // Calculate minimum moves
        int minMoves = n;
        // Special case: e.g., [1,2,3,6] or [1,4,5,6]
        // A block of n-1 consecutive stones with the nth stone far away.
        if ((stones[n - 2] - stones[0] == n - 2 && stones[n - 1] - stones[n - 2] > 1) || 
            (stones[n - 1] - stones[1] == n - 2 && stones[1] - stones[0] > 1)) {
            minMoves = 2;
        } else {
            int maxStonesInWindow = 0;
            // O(N^2) check for max stones in a window of size n
            for (int i = 0; i < n; i++) {
                int currentStonesInWindow = 0;
                long windowEnd = (long)stones[i] + n - 1;
                for (int j = 0; j < n; j++) {
                    if (stones[j] >= stones[i] && stones[j] <= windowEnd) {
                        currentStonesInWindow++;
                    }
                }
                maxStonesInWindow = Math.max(maxStonesInWindow, currentStonesInWindow);
            }
            minMoves = n - maxStonesInWindow;
        }

        return new int[]{minMoves, maxMoves};
    }
}
```
### Algorithm
- Sort the `stones` array in non-decreasing order.
- Calculate the maximum number of moves. This can be determined by considering two scenarios: keeping the leftmost `n-1` stones or the rightmost `n-1` stones as a group and moving the single endpoint. The number of moves is the number of empty slots within the span of the group. The formula is `max_moves = max(stones[n-1] - stones[1] - n + 2, stones[n-2] - stones[0] - n + 2)`.
- Calculate the minimum number of moves. The general idea is to find a window of size `n` that contains the maximum number of stones already. Let this count be `max_stones_in_window`. Then, the minimum moves would be `n - max_stones_in_window`.
- To find `max_stones_in_window`, iterate through each stone `stones[i]` as the potential start of a window. The window is `[stones[i], stones[i] + n - 1]`.
- For each such window, iterate through all stones `stones[j]` to count how many fall within this window's range. This is a nested loop structure.
- Keep track of the maximum count found across all windows.
- After finding the maximum count `max_k`, calculate the potential `min_moves` as `n - max_k`.
- Handle a special case: if there's a block of `n-1` consecutive stones with the last stone separated by a gap of more than one (e.g., `[1,2,3,6]`), it requires 2 moves. This needs to be checked explicitly. If this condition is met, `min_moves` is 2. Otherwise, it's `n - max_k`.
- Return the calculated `[min_moves, max_moves]`.

## Sorting and Sliding Window
This optimal approach also begins by sorting the `stones` array. The calculation for the maximum number of moves remains the same. The key improvement is in finding the minimum moves. Instead of a brute-force `O(N^2)` search for the best window, we use a sliding window (two-pointer) technique. We iterate through the sorted array with a right pointer `j` and maintain a left pointer `i` to define a 'window' of stones. We expand the window by incrementing `j` and shrink it by incrementing `i` whenever the span of the window (`stones[j] - stones[i] + 1`) exceeds the target length `n`. This allows us to find the maximum number of stones that can be contained in any `n`-length window in `O(N)` time. After finding this maximum count, `max_k`, the minimum moves is `n - max_k`, with a specific check for a special case that requires 2 moves.
**Time:** O(N log N), dominated by the initial sort. The sliding window part runs in O(N) time. · **Space:** O(N) or O(log N), for sorting. The sliding window itself uses O(1) extra space.
**Pros:** Highly efficient with `O(N log N)` time complexity, which passes for large inputs.; The sliding window technique is an elegant way to solve the subproblem of finding the maximum number of stones in a fixed-size window.
**Cons:** The logic, especially for the special case of minimum moves, can be subtle and requires careful handling.
### Explanation
The overall structure is similar to the first approach, but we optimize the calculation of `min_moves`.

**Sorting and Maximum Moves (`max_moves`)**
These steps are identical to the previous approach. We sort the array and use the `O(1)` formula for `max_moves`.
`max_moves = max(stones[n - 1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2)`.

**Minimum Moves (`min_moves`)**
The calculation is optimized using a sliding window. We first check for the same special case as before. If it doesn't apply, we proceed with the sliding window.
We use two pointers, `i` and `j`, to represent the start and end of a window of stones. We iterate `j` from `0` to `n-1` and for each `j`, we find the largest possible window ending at `j` whose span `stones[j] - stones[i] + 1` does not exceed `n`. This is done by advancing `i` whenever the span becomes too large. The number of stones in this window is `j - i + 1`. We track the maximum number of stones found in any such valid window (`max_k`). The minimum moves is then `n - max_k`.

```java
import java.util.Arrays;

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;

        // Calculate maximum moves
        // This is the max of empty slots if we fix the n-1 leftmost stones or n-1 rightmost stones.
        int maxMoves = Math.max(stones[n - 1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2);

        // Calculate minimum moves
        int minMoves = n;
        
        // Special case: e.g., [1,2,3,..,n-1, n+k] where k>1. It takes 2 moves.
        // e.g., [1,2,3,6] -> move 1 to 4 -> [2,3,4,6] -> move 6 to 5 -> [2,3,4,5]. 2 moves.
        // We can't move 6 to 4 directly as there's no space between 1 and 3.
        if ((stones[n - 2] - stones[0] == n - 2 && stones[n - 1] - stones[n - 2] > 1) || 
            (stones[n - 1] - stones[1] == n - 2 && stones[1] - stones[0] > 1)) {
            minMoves = 2;
        } else {
            // Sliding window to find max stones in a window of size n
            int i = 0;
            int maxStonesInWindow = 0;
            for (int j = 0; j < n; j++) {
                while (stones[j] - stones[i] + 1 > n) {
                    i++;
                }
                maxStonesInWindow = Math.max(maxStonesInWindow, j - i + 1);
            }
            minMoves = n - maxStonesInWindow;
        }

        return new int[]{minMoves, maxMoves};
    }
}
```
### Algorithm
- Sort the `stones` array in non-decreasing order.
- Calculate `max_moves` using the same `O(1)` formula as the previous approach: `max_moves = max(stones[n-1] - stones[1] - n + 2, stones[n-2] - stones[0] - n + 2)`.
- Calculate `min_moves` using an optimized method. First, handle the special case where `min_moves` is 2. This occurs if `n-1` stones are consecutive, but the `n`-th stone is separated by a gap of more than 1.
- If not a special case, find the maximum number of stones `max_k` that can fit into any window of size `n`. This is done efficiently using a sliding window (two-pointer) technique on the sorted array.
- Initialize two pointers, `i` (left) and `j` (right), both at 0. Iterate `j` from `0` to `n-1`.
- For each `j`, advance `i` as long as the current window `stones[j] - stones[i] + 1` is larger than `n`.
- The number of stones in the valid window `[i, j]` is `j - i + 1`. Keep track of the maximum value of this quantity, `max_k`.
- The minimum moves will be `n - max_k`.
- Return `[min_moves, max_moves]`.

# Solutions
### Java

```java
class Solution {
public
  int[] numMovesStonesII(int[] stones) {
    Arrays.sort(stones);
    int n = stones.length;
    int mi = n;
    int mx =
        Math.max(stones[n - 1] - stones[1] + 1, stones[n - 2] - stones[0] + 1) -
        (n - 1);
    for (int i = 0, j = 0; j < n; ++j) {
      while (stones[j] - stones[i] + 1 > n) {
        ++i;
      }
      if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2) {
        mi = Math.min(mi, 2);
      } else {
        mi = Math.min(mi, n - (j - i + 1));
      }
    }
    return new int[]{mi, mx};
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> numMovesStonesII(vector<int> &stones) {
    sort(stones.begin(), stones.end());
    int n = stones.size();
    int mi = n;
    int mx = max(stones[n - 1] - stones[1] + 1, stones[n - 2] - stones[0] + 1) -
             (n - 1);
    for (int i = 0, j = 0; j < n; ++j) {
      while (stones[j] - stones[i] + 1 > n) {
        ++i;
      }
      if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2) {
        mi = min(mi, 2);
      } else {
        mi = min(mi, n - (j - i + 1));
      }
    }
    return {mi, mx};
  }
};

```

### Python

```python
class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]: stones . sort() mi = n = len(stones) mx = max(stones[- 1] - stones[1] + 1, stones[- 2] - stones[0] + 1) - (n - 1) i = 0 for j, x in enumerate(stones): while x - stones[i] + 1 > n: i += 1 if j - i + 1 == n - 1 and x - stones[i] == n - 2: mi = min(mi, 2) else: mi = min(mi, n - (j - i + 1)) return [mi, mx]

```