Moving Stones Until Consecutive - Solution & Explanation
Problem Statement
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, andanswer[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 <= 100a,b, andchave different values.
Approach Overview
Problem Overview: You are given three integers representing positions of stones on a number line. In one move, you can pick up an endpoint stone and place it anywhere between the other two stones (but not at their positions). The goal is to make the stones occupy three consecutive positions. Return the minimum and maximum number of moves required.
Approach 1: Brute Reasoning with Gap Analysis (O(1) time, O(1) space)
With only three stones, the state space is tiny. Start by sorting the positions so you always work with a ≤ b ≤ c. The gaps b - a and c - b determine everything. If both gaps are already 1, the stones are consecutive and no moves are required. If either gap equals 2, you can slide the outer stone into the single missing slot in one move. Otherwise, you need two moves because each endpoint must move once to close the larger gaps.
The maximum moves come from moving endpoint stones one step inward at a time. After sorting, the total empty spaces between the outer stones is (c - a - 1). Since two stones already occupy positions inside that range, the number of remaining empty slots that must be filled through moves is (c - a - 2). Each move reduces this gap by exactly one, giving the maximum move count.
Approach 2: Sorting and Gap Calculation (Optimal) (O(1) time, O(1) space)
The clean solution sorts the three values and directly computes answers using simple arithmetic. After sorting, compute gap1 = b - a and gap2 = c - b. The minimum moves follow three cases: if gap1 == 1 and gap2 == 1, return 0; if either gap is ≤ 2, return 1; otherwise return 2. The maximum moves always equal (c - a - 2), which counts how many empty positions remain between the outer stones.
This works because every valid move must involve an endpoint stone, and the internal stone never moves. The structure of the problem collapses into simple arithmetic on the sorted coordinates rather than simulation. The logic falls under math reasoning and classic brainteaser pattern recognition rather than heavy data structures.
Recommended for interviews: Interviewers expect the sorting and gap calculation approach. It shows you recognize the invariant created by the three sorted positions and convert the game into a constant‑time math problem. Walking through the brute reasoning first demonstrates understanding of the move rules, while the final O(1) formula shows strong problem‑solving intuition.
Approach 1: Sorting and Gap Calculation
In this approach, we first sort the stone positions to determine the endpoints and calculate the gaps between consecutive stones. The minimum number of moves is determined by the distance between consecutive stones. If they're consecutive, no move is needed. For maximum moves, focus on bridging the largest gap first.
This C function first sorts the positions of the stones, calculates the gaps between them, and then determines the minimum and maximum number of moves based on these gaps.
Complexity
Time Complexity: O(1)
Space Complexity: O(1)
Approach 2: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting and Gap Calculation | Time Complexity: O(1) |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Reasoning with Gap Analysis | O(1) | O(1) | Useful when first reasoning about how endpoint moves affect gaps between stones |
| Sorting and Gap Calculation (Optimal) | O(1) | O(1) | Best approach for interviews and production; compute min and max moves directly from sorted positions |
Video Solution
Leetcode 1033- Math | Moving Stones | Brain Teaser and Math Calculations • Nideesh Terapalli • 1,545 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Moving Stones Until Consecutive easy or hard?
Moving Stones Until Consecutive Python/Java solution
How to solve Moving Stones Until Consecutive in O(1)?
What is the best approach for Moving Stones Until Consecutive?
Is Moving Stones Until Consecutive asked at Google/Amazon/Meta?
What data structure is used in Moving Stones Until Consecutive?
What is the time complexity of Moving Stones Until Consecutive?
Ready to solve this problem?
Practice Moving Stones Until Consecutive with our built-in code editor and test cases.
Practice on FleetCode