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

Function shape:

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

Examples

Example 1:

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:

[1, 2]

Example 2:

a, b, c = 4, 3, 2

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

Answer:

[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

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

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

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()