# LeetCode 1033: Moving Stones Until Consecutive

## Problem Restatement

Three stones are at positions `a`, `b`, `c` on a number line where `a < b < c`.

In one move, we pick the leftmost or rightmost stone and move it to an open position between the other two stones.

We need to return an array of two integers:

- `result[0]`: minimum number of moves.
- `result[1]`: maximum number of moves.

The official constraints state that `1 <= a, b, c <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Three integers `a`, `b`, `c` |
| Output | `[min_moves, max_moves]` |

Function shape:

```python
def numMovesStones(a: int, b: int, c: int) -> list[int]:
    ...
```

## Examples

Example 1:

```python
a, b, c = 1, 2, 5
```

Move `c=5` to `3`. Stones: `1, 2, 3`. Done in 1 move.

Min = 1. Max = ?

Max: Move `a=1` to `4` → `2, 4, 5`. Move `a=2` to `3` → `3, 4, 5`. That's 2 moves.

Answer:

```python
[1, 2]
```

Example 2:

```python
a, b, c = 4, 3, 2
```

After sorting: `2, 3, 4`. Already consecutive.

Answer:

```python
[0, 0]
```

## Key Insight

**Maximum moves**: The maximum is `(b - a - 1) + (c - b - 1)` — the total gaps minus the number of internal positions.

**Minimum moves**:
- If already consecutive: `0`.
- If one gap is 1 or 2 (one move places a stone right in the gap): `1`.
- Otherwise: `2` (bring each end stone one step closer).

## Algorithm

After sorting, let `x < y < z`.

- Max = `(y - x - 1) + (z - y - 1)`.
- Min:
  - If `y - x == 1 and z - y == 1`: `0`.
  - Elif `y - x <= 2 or z - y <= 2`: `1`.
  - Else: `2`.

## Correctness

For the maximum, we take one stone at a time from one end and place it just inside the other end, maximizing the number of moves.

For the minimum:
- If already consecutive, no moves needed.
- If one gap is exactly 1 or 2, we can close it in one move (place the outer stone just inside the opposite gap).
- Otherwise, two moves suffice: bring one end stone one step inside, then bring the other.

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | Constant work |
| Space | `O(1)` | No extra storage |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> list[int]:
        x, y, z = sorted([a, b, c])
        max_moves = (y - x - 1) + (z - y - 1)

        if y - x == 1 and z - y == 1:
            min_moves = 0
        elif y - x <= 2 or z - y <= 2:
            min_moves = 1
        else:
            min_moves = 2

        return [min_moves, max_moves]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numMovesStones(1, 2, 5) == [1, 2]
    assert s.numMovesStones(4, 3, 2) == [0, 0]
    assert s.numMovesStones(3, 5, 1) == [1, 2]
    assert s.numMovesStones(1, 10, 100) == [2, 96]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| `(1,2,5)` | `[1,2]` | Gap of 2 on right → 1 min move |
| `(4,3,2)` | `[0,0]` | Already consecutive |
| `(3,5,1)` | `[1,2]` | Gap of 2 after sorting |
| `(1,10,100)` | `[2,96]` | Large gaps → 2 min, 96 max |