LeetCode 1033 - Moving Stones Until Consecutive

The problem presents three stones placed on distinct positions along a one-dimensional X-axis, represented by integers a, b, and c.

leetcodemediummathbrainteaser

LeetCode Problem 1033

Difficulty: 🟡 Medium
Topics: Math, Brainteaser

Solution

Problem Understanding

The problem presents three stones placed on distinct positions along a one-dimensional X-axis, represented by integers a, b, and c. A move consists of taking a stone from one of the endpoints (the leftmost or rightmost stone) and placing it at an unoccupied position strictly between the endpoints. The goal is to determine two numbers: the minimum number of moves required to make the stones occupy three consecutive positions, and the maximum number of moves possible under the same rule.

The input guarantees that the three positions are distinct and bounded between 1 and 100, which makes brute-force feasible in principle, but the problem is designed to test insight rather than simulation. The output is always a list of two integers [min_moves, max_moves].

Important edge cases include stones that are already consecutive, stones that are spaced by exactly one empty position, or stones that are widely spaced. These situations affect both the minimum and maximum moves differently, so careful analysis is required.

Approaches

A brute-force approach would simulate all possible moves recursively, moving the endpoints into all valid positions between them until the stones are consecutive. While this guarantees correctness, it is unnecessary for this problem because the positions are limited to three stones. The simulation would involve checking all combinations, which is overkill.

The key insight is that with only three stones, the gaps between them dictate the answer directly. Let x < y < z be the sorted positions. Define gap1 = y - x - 1 and gap2 = z - y - 1. The minimum number of moves is determined by checking if either gap is 1 or 0: if one stone is only one move away from being consecutive, the minimum is 1; if both gaps are larger than 1, the minimum is 2. The maximum number of moves is simply moving stones one step at a time to fill the gaps, which is the sum gap1 + gap2.

Approach Time Complexity Space Complexity Notes
Brute Force O(?) O(?) Recursively simulate all possible moves until stones are consecutive; correct but unnecessary
Optimal O(1) O(1) Use gaps between sorted stones to compute min and max moves directly; constant time

Algorithm Walkthrough

  1. Sort the positions: Identify the leftmost, middle, and rightmost stones by sorting a, b, and c. Let x = min(a,b,c), z = max(a,b,c), and y the remaining middle value. Sorting simplifies gap calculations.
  2. Compute the gaps: Calculate gap1 = y - x - 1 and gap2 = z - y - 1. These represent the number of empty positions between stones.
  3. Determine the minimum moves: If either gap1 or gap2 is zero (stones are consecutive) or one (one empty space), only one move is needed to make the stones consecutive. Otherwise, if both gaps are larger than one, two moves are necessary, moving the stones from the endpoints to fill the gaps.
  4. Determine the maximum moves: The maximum number of moves occurs when moving one stone at a time to occupy intermediate positions. This is simply the sum gap1 + gap2.
  5. Return the result: Return a list [min_moves, max_moves].

Why it works: The sorted order ensures that x and z are always the endpoints, and the gaps represent exactly the empty positions to fill. The rules of the game limit moves to endpoints, so the min and max moves are fully determined by the gaps. This guarantees correctness without simulation.

Python Solution

from typing import List

class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        x, y, z = sorted([a, b, c])
        gap1 = y - x - 1
        gap2 = z - y - 1
        
        if gap1 == 0 and gap2 == 0:
            min_moves = 0
        elif gap1 <= 1 or gap2 <= 1:
            min_moves = 1
        else:
            min_moves = 2
        
        max_moves = gap1 + gap2
        return [min_moves, max_moves]

Explanation: The code first sorts the stone positions to simplify gap calculations. It then computes the number of empty positions between consecutive stones. The minimum moves are determined by checking if either gap is zero or one; the maximum moves are the sum of the gaps. The function returns the results as a list, matching the problem requirements.

Go Solution

func numMovesStones(a int, b int, c int) []int {
    // sort a, b, c
    x, y, z := a, b, c
    if x > y { x, y = y, x }
    if y > z { y, z = z, y }
    if x > y { x, y = y, x }
    
    gap1 := y - x - 1
    gap2 := z - y - 1
    
    minMoves := 0
    if gap1 == 0 && gap2 == 0 {
        minMoves = 0
    } else if gap1 <= 1 || gap2 <= 1 {
        minMoves = 1
    } else {
        minMoves = 2
    }
    
    maxMoves := gap1 + gap2
    return []int{minMoves, maxMoves}
}

Explanation: The Go version manually sorts the three integers using pairwise swaps. Gap calculations and logic for min and max moves mirror the Python version. The result is returned as a slice of integers.

Worked Examples

Example 1: a=1, b=2, c=5

Sorted: x=1, y=2, z=5

gap1 = 2-1-1 = 0, gap2 = 5-2-1 = 2

Minimum moves: gap1==0 → 1 move

Maximum moves: gap1 + gap2 = 0 + 2 = 2

Output: [1,2]

Example 2: a=4, b=3, c=2

Sorted: x=2, y=3, z=4

gap1 = 3-2-1 = 0, gap2 = 4-3-1 = 0

Minimum moves: 0 because stones already consecutive

Maximum moves: 0

Output: [0,0]

Example 3: a=3, b=5, c=1

Sorted: x=1, y=3, z=5

gap1 = 3-1-1=1, gap2 = 5-3-1=1

Minimum moves: gap1 <= 1 or gap2 <=1 → 1

Maximum moves: gap1 + gap2 = 2

Output: [1,2]

Complexity Analysis

Measure Complexity Explanation
Time O(1) Sorting three numbers and computing gaps is constant time
Space O(1) Only a fixed number of variables are used

The algorithm does not scale with input size because the problem size is fixed at three stones. No additional data structures are required, making it memory efficient.

Test Cases

# provided examples
assert Solution().numMovesStones(1, 2, 5) == [1, 2]  # gap1=0, gap2=2
assert Solution().numMovesStones(4, 3, 2) == [0, 0]  # already consecutive
assert Solution().numMovesStones(3, 5, 1) == [1, 2]  # gap1=1, gap2=1

# edge cases
assert Solution().numMovesStones(1, 3, 6) == [2, 4]  # two gaps larger than 1
assert Solution().numMovesStones(10, 11, 13) == [1, 2]  # one gap of 0, one gap of 1
assert Solution().numMovesStones(1, 50, 100) == [2, 147]  # large gaps
Test Why
1,2,5 Tests minimum gap zero and maximum gap >1
4,3,2 Already consecutive stones
3,5,1 Gaps equal to one, min move 1
1,3,6 Both gaps >1, min moves 2
10,11,13 One small gap, min move 1
1,50,100 Large gaps, tests maximum moves calculation

Edge Cases

The first important edge case is when the stones are already consecutive, like [2,3,4]. Here, both minimum and maximum moves are zero. The algorithm handles this by checking if both gaps are zero.

The second edge case is when one gap is exactly one, such as [1,3,5]. Only one move is needed to make the stones consecutive, even though the other gap is also one. The code handles this by using gap <= 1 in