LeetCode 2850 - Minimum Moves to Spread Stones Over Grid
This problem asks us to take a 3x3 grid of integers representing stones in each cell and redistribute them so that every cell contains exactly one stone. Each move consists of moving a stone from one cell to a directly adjacent cell (sharing a side, not a diagonal).
Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Matrix, Bitmask
Solution
Problem Understanding
This problem asks us to take a 3x3 grid of integers representing stones in each cell and redistribute them so that every cell contains exactly one stone. Each move consists of moving a stone from one cell to a directly adjacent cell (sharing a side, not a diagonal). The goal is to minimize the total number of moves required to reach the uniform state where each of the nine cells has exactly one stone.
The input grid is always 3x3, and the total sum of stones is guaranteed to be 9. This guarantees that a solution always exists. Edge cases to consider include cells that start with zero stones, cells with multiple stones (up to 9), and situations where all stones are concentrated in a few cells. The adjacency restriction means we must consider the Manhattan distance between source and destination cells when counting moves.
The expected output is a single integer representing the minimum number of moves.
Approaches
The brute-force approach would enumerate all sequences of moves to place stones until the grid is uniform. At each step, we could move a stone to any adjacent cell and recursively continue until the grid satisfies the target. This approach is guaranteed to eventually find the minimum because it explores all possibilities, but the number of possible move sequences grows explosively. Considering each stone can move in 2 to 4 directions and multiple stones exist in one cell, this is combinatorially infeasible, even for a 3x3 grid.
The key insight for an optimal solution is that because the grid is small (3x3), we can represent the distribution of stones as a flat array and compute all positions with surplus and deficit. Then, we can use backtracking with memoization or bitmasking to explore the minimum moves efficiently. The move cost between two cells is simply the Manhattan distance, so the problem reduces to pairing surplus stones to empty cells with minimal total Manhattan distance.
A simpler, practical solution leverages DFS/backtracking with pruning, enumerating all possible distributions of surplus stones to empty cells, summing the Manhattan distances, and keeping track of the minimum sum. Because the grid is small, this solution runs fast enough.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(4^9) | O(1) | Tries all move sequences explicitly; combinatorially infeasible |
| Optimal | O(9! * 2^9) | O(2^9) | Use backtracking with Manhattan distances and memoization; feasible because grid size is fixed |
Algorithm Walkthrough
- Flatten the grid: Convert the
3x3grid into a list of(row, col)pairs representing the cells with stones. Record how many stones are in each cell. - Identify surplus and deficit cells: Any cell with more than one stone is a surplus, and any cell with zero stones is a deficit.
- Define a recursive function: The function takes the current index of surplus stones to assign, a tuple representing the current deficit cells, and computes the minimal cost recursively.
- Compute moves: For each surplus stone, try moving it to any deficit cell. The cost is the Manhattan distance between the source and target cells.
- Update state and recurse: After moving a stone, update the surplus and deficit counts and recurse to assign the next stone.
- Memoization: Store computed results for a given surplus-deficit state to avoid recalculating subproblems.
- Return minimum moves: After exploring all configurations, return the smallest sum of Manhattan distances, representing the minimum number of moves.
Why it works: Each move is counted as the Manhattan distance between a stone’s current position and its final position. Because all stones are indistinguishable and the grid is small, exhaustive exploration with pruning guarantees the minimal total distance is found.
Python Solution
from typing import List
from functools import lru_cache
class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
stones = []
empties = []
for i in range(3):
for j in range(3):
count = grid[i][j]
if count == 0:
empties.append((i, j))
elif count > 1:
for _ in range(count - 1):
stones.append((i, j))
@lru_cache(None)
def dfs(index, empty_mask):
if index == len(stones):
return 0
min_cost = float('inf')
for i, (r, c) in enumerate(empties):
if not (empty_mask & (1 << i)):
cost = abs(stones[index][0] - r) + abs(stones[index][1] - c)
min_cost = min(min_cost, cost + dfs(index + 1, empty_mask | (1 << i)))
return min_cost
return dfs(0, 0)
Explanation: First, we identify surplus stones and empty cells. stones contains positions of all extra stones, and empties contains positions of empty cells. The dfs function recursively assigns each surplus stone to an empty cell, computing the Manhattan distance as the move cost. empty_mask is used as a bitmask to track which empty cells have been filled. Memoization with lru_cache ensures repeated states are computed only once.
Go Solution
func minimumMoves(grid [][]int) int {
type pos struct{ r, c int }
stones := []pos{}
empties := []pos{}
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
count := grid[i][j]
if count == 0 {
empties = append(empties, pos{i, j})
} else if count > 1 {
for k := 0; k < count-1; k++ {
stones = append(stones, pos{i, j})
}
}
}
}
memo := map[int]int{}
var dfs func(int, int) int
dfs = func(index, mask int) int {
if index == len(stones) {
return 0
}
key := mask | (index << 16)
if v, ok := memo[key]; ok {
return v
}
res := 1 << 30
for i, e := range empties {
if mask&(1<<i) == 0 {
cost := abs(stones[index].r-e.r) + abs(stones[index].c-e.c)
res = min(res, cost+dfs(index+1, mask|(1<<i)))
}
}
memo[key] = res
return res
}
return dfs(0, 0)
}
func abs(a int) int {
if a < 0 { return -a }
return a
}
func min(a, b int) int {
if a < b { return a }
return b
}
Go differences: We use a struct pos to represent cell coordinates. Memoization uses a map keyed by combining the index and bitmask. Bit operations manage filled empty cells. Functions abs and min are defined explicitly because Go does not provide them for integers by default.
Worked Examples
Example 1: grid = [[1,1,0],[1,1,1],[1,2,1]]
Surplus stones: one at (2,1)
Empty cells: (0,2)
- Move stone from (2,1) to (2,2) cost = 1
- Move stone from (2,2) to (1,2) cost = 1
- Move stone from (1,2) to (0,2) cost = 1
Total moves = 3
Example 2: grid = [[1,3,0],[1,0,0],[1,0,3]]
Surplus stones: two at (0,1), two at (2,2)
Empty cells: (0,2), (1,1), (1,2), (2,1)
Optimal assignment minimizes total Manhattan distance = 4 moves
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(9! * 2^9) | There are at most 8 surplus stones and 8 empty cells; recursive assignment with bitmask memoization bounds complexity |
| Space | O(2^9) | Memoization table for bitmask states and recursion stack up to 8 levels deep |
The time complexity is acceptable because the number of stones is fixed and small (<=8), making exhaustive assignment feasible with memoization.
Test Cases
# Provided examples
assert Solution().minimumMoves([[1,1,0],[1,1,1],[1,2,1]]) == 3 # basic example
assert Solution().minimumMoves([[1,3,0],[1,0,0],[1,0,3]]) == 4 # more complex redistribution
# Edge cases
assert Solution().minimumMoves([[9,0,0],[0,0,0],[0,0,0]]) == 12 # all stones in one cell
assert Solution().minimumMoves([[1,1,1],[1,1,1],[1,1,1]]) == 0 # already balanced
assert Solution().minimumMoves([[2,1,1