Minimum Moves to Spread Stones Over Grid - Solution & Explanation
Problem Statement
You are given a 0-indexed 2D integer matrix grid of size 3 * 3, representing the number of stones in each cell. The grid contains exactly 9 stones, and there can be multiple stones in a single cell.
In one move, you can move a single stone from its current cell to any other cell if the two cells share a side.
Return the minimum number of moves required to place one stone in each cell.
Example 1:
Input: grid = [[1,1,0],[1,1,1],[1,2,1]] Output: 3 Explanation: One possible sequence of moves to place one stone in each cell is: 1- Move one stone from cell (2,1) to cell (2,2). 2- Move one stone from cell (2,2) to cell (1,2). 3- Move one stone from cell (1,2) to cell (0,2). In total, it takes 3 moves to place one stone in each cell of the grid. It can be shown that 3 is the minimum number of moves required to place one stone in each cell.
Example 2:
Input: grid = [[1,3,0],[1,0,0],[1,0,3]] Output: 4 Explanation: One possible sequence of moves to place one stone in each cell is: 1- Move one stone from cell (0,1) to cell (0,2). 2- Move one stone from cell (0,1) to cell (1,1). 3- Move one stone from cell (2,2) to cell (1,2). 4- Move one stone from cell (2,2) to cell (2,1). In total, it takes 4 moves to place one stone in each cell of the grid. It can be shown that 4 is the minimum number of moves required to place one stone in each cell.
Constraints:
grid.length == grid[i].length == 30 <= grid[i][j] <= 9- Sum of
gridis equal to9.
Approach Overview
Problem Overview: You are given a 3×3 grid containing exactly 9 stones, but some cells may hold multiple stones while others are empty. In one move, you can move a stone to an adjacent cell (up, down, left, right). The goal is to redistribute the stones so every cell contains exactly one stone while minimizing the number of moves.
Approach 1: Breadth-First Search (State Exploration) (Time: O(S), Space: O(S))
This approach treats the entire grid configuration as a state and performs a Breadth-First Search to find the shortest sequence of moves that leads to the target configuration where every cell contains exactly one stone. Each state is encoded as a 9-element array or string representing the grid. From a given state, generate neighbors by moving a stone from any cell with more than one stone to an adjacent cell. A visited set prevents revisiting configurations. Since BFS expands level by level, the first time you reach the valid configuration guarantees the minimum number of moves.
Approach 2: DFS with Backtracking (Assignment Search) (Time: O(k!), Space: O(k))
Instead of exploring grid states, this method focuses on matching surplus stones with empty cells. First iterate through the matrix and record coordinates of cells with extra stones and coordinates of empty cells. Then use depth‑first search with backtracking to assign each extra stone to an empty position. The cost of assigning a stone at (r1, c1) to (r2, c2) is the Manhattan distance |r1-r2| + |c1-c2|, which equals the minimum number of adjacent moves required. Try all permutations of assignments and track the minimum total cost. Because the grid is small (at most 6 extra stones), the factorial search space remains manageable.
Approach 3: Greedy Distance Matching (Time: O(k log k), Space: O(k))
A simpler strategy collects all extra stone positions and all empty cells, then pairs them based on distance. Compute the Manhattan distance between each surplus stone and candidate empty cells and greedily move stones to the nearest target. The key insight is that moving a stone step‑by‑step across the grid effectively accumulates Manhattan distance. While this heuristic often works due to the small grid size, it does not guarantee optimality in every theoretical arrangement. It is useful for quick reasoning and interview discussions when explaining the movement cost model.
Approach 4: BFS with Distance Modeling (Time: O(k! * k), Space: O(k))
Another variation builds the solution by repeatedly moving surplus stones toward empty cells using BFS distance calculations. For each extra stone, compute the shortest path distance to each empty cell and explore combinations. This approach blends graph traversal with assignment search and highlights how shortest paths on a grid correspond to Manhattan distance in unobstructed cases.
Recommended for interviews: The DFS backtracking assignment is the most commonly expected solution. It clearly models the problem as matching extra stones to empty cells and demonstrates strong reasoning about Manhattan distance and permutation search. BFS over full grid states proves correctness but introduces larger state space overhead. Mentioning both shows solid understanding of array manipulation and graph traversal techniques.
Approach 1: Breadth-First Search (BFS) Approach
The BFS approach treats the grid as a graph where each cell is a node connected to its neighboring nodes (up, down, left, right if within bounds). Starting from any node with excess stones, we move adjacent nodes trying to reach a balance where each cell contains exactly one stone.
This approach maintains a queue of states representing stone distributions and explores all possible moves layer by layer to ensure the minimum transformation sequence.
The function minMoves initializes a queue with the starting configuration of stones in a 1D list format. It uses BFS to explore each state iteratively while checking if the state matches the target state where every cell contains exactly one stone. When an excess of stones is found in a cell, it checks all possible adjacent moves and enqueues new states while maintaining a set of visited states for optimization purposes.
Code
Python
Complexity
Time Complexity: O(n!) where n is the number of excess stones due to factorial possibilities of distribution.
Space Complexity: O(n) for storing visited states and queue elements.
Approach 2: Depth-First Search (DFS) with Backtracking
The DFS approach explores possible distributions in a recursive manner, backtracking when a path doesn't yield an optimal solution. Starting from any node with excess stones, it attempts to transfer stones one by one to neighboring deficit nodes, recursively exploring deeper transfers.
This approach ensures that each path is explored thoroughly, maximizing the chances of reaching an optimal sequence.
The code implements a helper function dfs to recursively explore all possible moves until reaching a configuration where each cell contains exactly one stone. The function isTarget checks if the current grid state matches the target state. Backtracking ensures that stones can be moved back before testing new paths, thereby consistently looking for the shortest sequence of moves.
Code
Java
Complexity
Time Complexity: Potentially large due to exhaustive exploration, but practical for a 3x3 grid due to fixed size.
Space Complexity: O(1) additional storage, apart from the call stack.
Approach 3: Greedy Approach
Approach Description: The greedy approach involves iterating over each cell of the grid and balancing the surplus and deficit of stones in adjacent cells using the fewest moves necessary. By systematically balancing each row or column, we can ensure all cells contain exactly one stone.
This code moves stones first horizontally and then vertically. It calculates the surplus or deficit and makes necessary adjustments to achieve a grid where each cell holds exactly one stone. The total moves required are accumulated efficiently.
Complexity
Time Complexity: O(1) since it's always a 3x3 grid. Space Complexity: O(1) as no additional storage is needed except for counting moves.
Approach 4: Breadth-First Search (BFS)
Approach Description: Use a BFS approach where each state of the grid represents a node. Each transition (move) generates a new node. BFS systematically explores each node, exploring all possible grid configurations, calculating the minimal number of moves to reach a goal state of each cell containing exactly one stone.
The BFS function explores all possible states of the grid, using a queue to track the minimum number of moves to reach each state. It terminates when the goal configuration (one stone per cell) is found, returning the corresponding move count.
Code
Python
Complexity
Time Complexity: O((3*3)!) which can be significant due to factorial growth in permutations of grid states. Space Complexity: O((3*3)!) due to storing states and their transitions.
Approach 5: Naive BFS
The problem is essentially finding the shortest path from the initial state to the target state in a state graph, so we can use BFS to solve it. The initial state is grid, and the target state is [[1, 1, 1], [1, 1, 1], [1, 1, 1]]. In each operation, we can move a stone greater than 1 from a cell to an adjacent cell that does not exceed 1. If the target state is found, we can return the current layer number, which is the minimum number of moves.
Code
Python
Java
C++
Go
TypeScript
Approach 6: State Compression Dynamic Programming
We can put all the coordinates (i, j) of cells with a value of 0 into an array left. If the value v of a cell is greater than 1, we put v-1 coordinates (i, j) into an array right. The problem then becomes that each coordinate (i, j) in right needs to be moved to a coordinate (x, y) in left, and we need to find the minimum number of moves.
Let's denote the length of left as n. We can use an n-bit binary number to represent whether each coordinate in left is filled by a coordinate in right, where 1 represents being filled, and 0 represents not being filled. Initially, f[i] = infty, and the rest f[0]=0.
Consider f[i], let the number of 1s in the binary representation of i be k. We enumerate j in the range [0..n), if the jth bit of i is 1, then f[i] can be transferred from f[i \oplus (1 << j)], and the cost of the transfer is cal(left[k-1], right[j]), where cal represents the Manhattan distance between two coordinates. The final answer is f[(1 << n) - 1].
The time complexity is O(n times 2^n), and the space complexity is O(2^n). Here, n is the length of left, and in this problem, n \le 9.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n!) where n is the number of excess stones due to factorial possibilities of distribution. |
| Depth-First Search (DFS) with Backtracking | Time Complexity: Potentially large due to exhaustive exploration, but practical for a 3x3 grid due to fixed size. |
| Greedy Approach | Time Complexity: O(1) since it's always a 3x3 grid. Space Complexity: O(1) as no additional storage is needed except for counting moves. |
| Breadth-First Search (BFS) | Time Complexity: O((3*3)!) which can be significant due to factorial growth in permutations of grid states. Space Complexity: O((3*3)!) due to storing states and their transitions. |
| Naive BFS | — |
| State Compression Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS State Exploration | O(S) | O(S) | When modeling the problem as shortest path between grid states |
| DFS with Backtracking (Assignment) | O(k!) | O(k) | Best practical solution due to small number of extra stones |
| Greedy Distance Matching | O(k log k) | O(k) | Quick heuristic when optimal pairing is obvious |
| BFS Distance + Assignment | O(k! * k) | O(k) | Useful for understanding shortest path movement on grids |
Video Solution
Leetcode Weekly contest 362 - Medium - Minimum Moves to Spread Stones Over Grid • Prakhar Agrawal • 6,083 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Moves to Spread Stones Over Grid easy or hard?
Minimum Moves to Spread Stones Over Grid Python/Java solution
How to solve Minimum Moves to Spread Stones Over Grid in O(n)?
What is the best approach for Minimum Moves to Spread Stones Over Grid?
Is Minimum Moves to Spread Stones Over Grid asked at Google/Amazon/Meta?
What data structure is used in Minimum Moves to Spread Stones Over Grid?
What is the time complexity of Minimum Moves to Spread Stones Over Grid?
Ready to solve this problem?
Practice Minimum Moves to Spread Stones Over Grid with our built-in code editor and test cases.
Practice on FleetCode