Abstract / Summary

Move the fewest stones so all are in consecutive spots on a line.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (60k+ submissions).

Typical patterns to solve this problem:

• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The numMovesStones method receives three integer positions of stones on a number line and returns a two-element list. The first element is the minimum number of moves required to make the stones occupy three consecutive positions, and the second element is the maximum number of moves possible while still ending with a consecutive configuration. The implementation follows a deterministic, constant-time approach that relies on sorting the inputs and evaluating the gaps between them.

Key Steps

The method begins by arranging the three input positions in ascending order. This guarantees that subsequent calculations can refer to the stones by their relative order without additional conditionals.

all = sorted([a, b, c])

A variable low is initialized to zero and is incremented based on the distances between the sorted stones. The first conditional checks whether the leftmost gap is larger than one, indicating that the left stone can be moved closer to the middle stone.

low = 0
if all[1] - all[0] != 1:  # move closer to middle
    low += 1

The second conditional mirrors the first check for the rightmost gap.

if all[2] - all[1] != 1:  # move closer to middle
    low += 1

A special case is handled when either gap equals exactly two. In such a scenario, a single move can place the middle stone directly between the other two, achieving a consecutive arrangement in one step. The code overrides any previous count and sets low to one.

if all[2] - all[1] == 2 or all[1] - all[0] == 2:  # move between the other two
    low = 1

The maximum number of moves, high, is derived from the total span between the outer stones minus the two positions that will remain occupied in the final consecutive state. This expression captures the worst-case scenario where each move shifts a stone only one position toward the center.

high = all[2] - all[0] - 2

Finally, the method returns the computed minimum and maximum move counts as a list.

return [low, high]

Edge Cases Handled

When the three stones are already consecutive, both gaps equal one. The first two conditionals do not increment low, and the special case does not trigger because neither gap equals two. Consequently, low remains zero, correctly indicating that no moves are needed. The high calculation yields all[2] - all[0] - 2, which evaluates to zero in this configuration, reflecting that no moves can be made while preserving a consecutive arrangement.

If exactly one gap equals two while the other gap is larger than one, the special case forces low to one. This captures the situation where a single move can close the two-position gap by placing the middle stone directly between the outer stones, achieving consecutiveness in the minimal possible steps.

When both gaps are larger than two, the first two conditionals each add one to low, resulting in a minimum of two moves. This reflects the necessity of moving each outer stone at least once to close the larger gaps. The special case does not apply because neither gap equals two, preserving the two-move minimum.

Performance Optimizations

The algorithm operates in constant time, performing a fixed number of arithmetic and comparison operations regardless of input values. Sorting three elements is effectively a constant-time operation due to the small, bounded size, and the subsequent logic avoids any loops or recursion. By directly computing the maximum moves through a simple arithmetic expression, the implementation eliminates the need for iterative simulation of each move, thereby minimizing runtime overhead. The use of in-place variable updates (low += 1) and immediate overrides for the special case further streamline the execution path.

Imagine there are three little rocks sitting in a line on a path. Each rock is at a different spot, and there might be gaps between them. The goal is to move the rocks until they are all touching each other with no empty spaces in between.

First, the code puts the rocks in order from the smallest number to the largest number so they are easy to look at.

To figure out the fewest number of moves, the code checks the gaps between the rocks. If there is a big gap, a rock has to hop over. If the rocks are already sitting next to each other, they do not need to move at all. Sometimes, a single jump is enough to get them all touching.

To figure out the most moves possible, the code assumes each rock moves one tiny step at a time until they are all side by side. It counts every single empty spot between the first rock and the last rock, and that shows how far they can travel to get together.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java		TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python			Java	Go	TS
	LeetcodeHelp	C++	Python			Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python			Java
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai					Java
	everthis			JS
	fsq	C++
	Garvit244		Python
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM				C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
Garvit244	Python
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality