# Moving Stones Until Consecutive
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/moving-stones-until-consecutive)
Canonical: https://scaleengineer.com/dsa/problems/moving-stones-until-consecutive
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
There are three stones in different positions on the X-axis. You are given three integers `a`, `b`, and `c`, the positions of the stones.

In one move, you pick up a stone at an endpoint (i.e., either the lowest or highest position stone), and move it to an unoccupied position between those endpoints. Formally, let's say the stones are currently at positions `x`, `y`, and `z` with `x < y < z`. You pick up the stone at either position `x` or position `z`, and move that stone to an integer position `k`, with `x < k < z` and `k != y`.

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:** a = 1, b = 2, c = 5
**Output:** [1,2]
**Explanation:** Move the stone from 5 to 3, or move the stone from 5 to 4 to 3.

**Example 2:**

**Input:** a = 4, b = 3, c = 2
**Output:** [0,0]
**Explanation:** We cannot make any moves.

**Example 3:**

**Input:** a = 3, b = 5, c = 1
**Output:** [1,2]
**Explanation:** Move the stone from 1 to 4; or move the stone from 1 to 2 to 4.

**Constraints:**

* `1 <= a, b, c <= 100`
* `a`, `b`, and `c` have different values.

# Approaches
## Brute Force Simulation using BFS
This approach models the problem as finding the shortest path in a state graph. Each state is represented by the sorted positions of the three stones. We use Breadth-First Search (BFS) to explore states level by level, which guarantees finding the minimum number of moves required. While this method is general and robust for shortest path problems, it is computationally expensive for this particular problem.
**Time:** O(N^4), where N is the maximum coordinate value. The number of states is O(N^3), and from each state, we can generate O(N) next states. · **Space:** O(N^3), where N is the maximum possible coordinate value. This is for the `visited` set, as there can be up to O(N^3) distinct stone configurations.
**Pros:** Guaranteed to find the optimal minimum number of moves.; It is a general approach applicable to many shortest path problems on graphs.
**Cons:** High time and space complexity, making it impractical for larger coordinate ranges.; Significantly more complex to implement correctly compared to the mathematical approach.; It is an overkill for this problem, as a much simpler solution exists.
### Explanation
The core idea is to treat every possible arrangement of the three stones as a node in a graph. An edge exists from one arrangement to another if you can get there in a single move. The problem of finding the minimum number of moves then becomes equivalent to finding the shortest path from the initial arrangement to any arrangement where the stones are consecutive.

BFS is the ideal algorithm for this because it explores the graph layer by layer, ensuring that the first time we reach a target state, it is via a shortest path.

The algorithm for finding the minimum moves is as follows:
1.  Start with the initial sorted positions `(x, y, z)`.
2.  Use a queue for the BFS and a `Set` to store visited states to prevent re-processing and infinite loops.
3.  Add the initial state to the queue and the visited set.
4.  The BFS proceeds in levels, where each level corresponds to one move. We keep a count of the current level.
5.  In each step, we dequeue a state and generate all possible next states by moving either the leftmost or the rightmost stone to an empty position between them.
6.  If a generated state is new, we enqueue it and add it to our visited set.
7.  The search terminates when we find a state where the stones are consecutive (e.g., `3, 4, 5`). The number of levels we have traversed at that point is the minimum number of moves.

The maximum number of moves can be calculated directly with the formula `z - x - 2`, so we don't need to simulate for it.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int[] initialStones = {a, b, c};
        Arrays.sort(initialStones);
        int x = initialStones[0];
        int y = initialStones[1];
        int z = initialStones[2];

        // Maximum moves is the number of empty slots between endpoints.
        int maxMoves = z - x - 2;

        // Minimum moves using BFS
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        queue.offer(initialStones);
        visited.add(Arrays.toString(initialStones));
        
        int minMoves = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] current = queue.poll();
                int curX = current[0];
                int curY = current[1];
                int curZ = current[2];

                if (curZ - curX == 2) { // Stones are consecutive
                    return new int[]{minMoves, maxMoves};
                }

                // Generate next states by moving an endpoint stone to a position 'k'
                // where curX < k < curZ and k != curY.
                
                // Move stone from curX to k
                int[] nextConfig1 = new int[]{curY, curZ, 0};
                for (int k = curX + 1; k < curZ; k++) {
                    if (k == curY) continue;
                    nextConfig1[2] = k;
                    Arrays.sort(nextConfig1);
                    String nextState = Arrays.toString(nextConfig1);
                    if (!visited.contains(nextState)) {
                        visited.add(nextState);
                        queue.offer(new int[]{nextConfig1[0], nextConfig1[1], nextConfig1[2]});
                    }
                }

                // Move stone from curZ to k
                int[] nextConfig2 = new int[]{curX, curY, 0};
                for (int k = curX + 1; k < curZ; k++) {
                    if (k == curY) continue;
                    nextConfig2[2] = k;
                    Arrays.sort(nextConfig2);
                    String nextState = Arrays.toString(nextConfig2);
                    if (!visited.contains(nextState)) {
                        visited.add(nextState);
                        queue.offer(new int[]{nextConfig2[0], nextConfig2[1], nextConfig2[2]});
                    }
                }
            }
            minMoves++;
        }
        
        return new int[]{0, maxMoves}; // Should not be reached
    }
}
```
### Algorithm
- Sort the initial stone positions `a, b, c` to get a canonical representation `(x, y, z)`.
- To find the maximum number of moves, use the formula `max_moves = z - x - 2`.
- To find the minimum number of moves, model the problem as finding the shortest path in a state graph using Breadth-First Search (BFS).
- Each state is a tuple `(x, y, z)` of sorted stone positions.
- Initialize a queue with the starting state and a `visited` set to avoid cycles.
- Perform BFS level by level. The number of levels traversed is the number of moves.
- In each level, explore all possible next states by moving an endpoint stone (`x` or `z`) to an unoccupied position `k` between the endpoints (`x < k < z`, `k != y`).
- For each new valid state, if it has not been visited, add it to the queue and the `visited` set.
- The first time a state `(x, y, z)` is reached where `z - x == 2` (i.e., the stones are consecutive), the current level count is the minimum number of moves.

## Constant Time Mathematical Approach
This approach leverages mathematical insights and case analysis to solve the problem in constant time. By examining the gaps between the sorted stone positions, we can derive direct formulas for both the minimum and maximum number of moves without any simulation. This is the most efficient way to solve the problem.
**Time:** O(1), because sorting three elements takes constant time, and the rest of the logic involves a few arithmetic operations and comparisons. · **Space:** O(1), as we only use a few variables to store the stone positions. Sorting an array of size 3 is also a constant space operation.
**Pros:** Extremely efficient, with O(1) time complexity.; Requires only constant extra space.; The implementation is very simple and concise once the logic is understood.
**Cons:** The logic relies on careful case analysis. An error in reasoning can lead to an incorrect solution.; It is less intuitive than a brute-force simulation for those not accustomed to this type of combinatorial reasoning.
### Explanation
After sorting the stone positions as `x, y, z`, we can determine the minimum and maximum moves by analyzing the spaces between them.

**Maximum Moves:**
To maximize the number of moves, we want to make the smallest possible change in each step. A move consists of taking an endpoint stone and placing it in an empty slot between the endpoints. The total number of empty slots is `(z - x + 1) - 3 = z - x - 2`. We can make one move for each empty slot by moving an endpoint stone one unit at a time (e.g., moving `x` to `x+1`, then `x+1` to `x+2`, etc.). Thus, the maximum number of moves is `z - x - 2`.

**Minimum Moves:**
For the minimum moves, we consider the following cases:
1.  **0 Moves:** If the stones are already consecutive, like `(3, 4, 5)`, then `z - y = 1` and `y - x = 1`, which implies `z - x = 2`. No moves are needed.
2.  **1 Move:** If we can place one of the endpoint stones to make the three consecutive. This is possible if one of the gaps is small. For example, if we have `(x, x+2, z)`, the gap `y-x` is 2. We can move stone `z` to `x+1` in one move. Similarly, if we have `(x, y, y+2)`, we can move `x` to `y+1`. This logic extends to when a gap is 1 (e.g., `(x, x+1, z)`). So, if `y - x <= 2` or `z - y <= 2`, the minimum is 1 move.
3.  **2 Moves:** If neither of the above cases applies, it means both gaps are large (`y - x > 2` and `z - y > 2`). We can always solve this in two moves. First, move an endpoint stone to be adjacent to the middle stone (e.g., move `x` to `y-1`). This creates a configuration like `(y-1, y, z)`, which we know from the previous case can be solved in one more move. Therefore, the minimum is 2 moves.

This case analysis covers all possibilities and provides the answer directly.

```java
import java.util.Arrays;

class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int[] stones = {a, b, c};
        Arrays.sort(stones);
        
        int x = stones[0];
        int y = stones[1];
        int z = stones[2];
        
        // Calculate maximum moves
        // This is the total number of empty slots between the endpoints.
        int maxMoves = z - x - 2;
        
        // Calculate minimum moves
        int minMoves;
        if (z - x == 2) {
            // Already consecutive, e.g., (3, 4, 5)
            minMoves = 0;
        } else if (y - x <= 2 || z - y <= 2) {
            // One move is enough if one of the gaps is small.
            // e.g., (3, 5, 8) -> move 8 to 4 -> (3, 4, 5)
            // e.g., (3, 4, 8) -> move 8 to 5 -> (3, 4, 5)
            minMoves = 1;
        } else {
            // Two moves are needed otherwise.
            // e.g., (1, 5, 10) -> move 1 to 4 -> (4, 5, 10) -> move 10 to 6 -> (4, 5, 6)
            minMoves = 2;
        }
        
        return new int[]{minMoves, maxMoves};
    }
}
```
### Algorithm
- First, sort the three stone positions `a, b, c` and let them be `x, y, z` such that `x < y < z`.
- **Calculate Maximum Moves**: The maximum number of moves is the total number of empty integer slots between the two outer stones. This can be calculated as `z - x - 2`.
- **Calculate Minimum Moves**: This requires a case-by-case analysis based on the gaps between the stones.
  - **Case 1: 0 moves.** If the stones are already consecutive, no moves are possible. This is true if `z - x == 2`.
  - **Case 2: 1 move.** If either of the gaps between adjacent stones is small enough (less than 2 empty slots), we can achieve a consecutive arrangement in one move. This condition is met if `y - x <= 2` or `z - y <= 2`.
  - **Case 3: 2 moves.** If neither of the above conditions is met, it means both gaps are large (`y - x > 2` and `z - y > 2`). In this scenario, it always takes exactly two moves to make the stones consecutive.
- Return the calculated minimum and maximum moves as an array `[min_moves, max_moves]`.

# Solutions
### Java

```java
class Solution { public int [] numMovesStones ( int a , int b , int c ) { int x = Math . min ( a , Math . min ( b , c )); int z = Math . max ( a , Math . max ( b , c )); int y = a + b + c - x - z ; int mi = 0 , mx = 0 ; if ( z - x > 2 ) { mi = y - x < 3 || z - y < 3 ? 1 : 2 ; mx = z - x - 2 ; } return new int [] { mi , mx }; } }
```

### CPP

```cpp
class Solution { public: vector < int > numMovesStones ( int a , int b , int c ) { int x = min ({ a , b , c }); int z = max ({ a , b , c }); int y = a + b + c - x - z ; int mi = 0 , mx = 0 ; if ( z - x > 2 ) { mi = y - x < 3 || z - y < 3 ? 1 : 2 ; mx = z - x - 2 ; } return { mi , mx }; } };
```

### Python

```python
class Solution : def numMovesStones ( self , a : int , b : int , c : int ) -> List [ int ]: x , z = min ( a , b , c ), max ( a , b , c ) y = a + b + c - x - z mi = mx = 0 if z - x > 2 : mi = 1 if y - x < 3 or z - y < 3 else 2 mx = z - x - 2 return [ mi , mx ]
```