Minimum Moves to Spread Stones Over Grid
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach formulates the problem as a classic assignment problem. We need to move extra stones from 'source' cells (more than one stone) to 'destination' cells (zero stones). The goal is to find a one-to-one mapping between the extra stones and empty cells that minimizes the total number of moves. Since the number of stones to move is small (at most 8), we can explore every possible assignment. This is equivalent to generating all permutations of the destination cells and calculating the total cost for each.
Algorithm
- Identify cells with more than one stone (sources) and cells with zero stones (destinations).
- Create a list
excessStonescontaining the coordinates of each extra stone. If a cell hasgstones, its coordinate is addedg-1times. - Create a list
emptyCellscontaining the coordinates of each empty cell. - Generate all possible permutations of the
emptyCellslist. - For each permutation, calculate the total cost by summing the Manhattan distances between the
i-th stone inexcessStonesand thei-th cell in the permutedemptyCellslist. - The minimum cost found among all permutations is the answer.
Walkthrough
The core idea is to perform a brute-force search over all possible pairings of surplus stones with empty cells.
-
Identify Sources and Destinations: First, we iterate through the 3x3 grid to find two types of cells:
- Cells with
grid[i][j] > 1: These are sources of extra stones. For each such cell, we add its coordinates(i, j)to a list calledexcessStonesexactlygrid[i][j] - 1times. - Cells with
grid[i][j] == 0: These are empty cells that need a stone. We add their coordinates(i, j)to a list calledemptyCells.
- Cells with
-
Generate Permutations: The problem is now to match each stone in
excessStonesto a unique cell inemptyCells. We can solve this by trying every possible permutation of theemptyCellslist. For each permutation, we pair the first excess stone with the first cell in the permuted list, the second stone with the second cell, and so on. -
Calculate Cost: For each complete pairing (permutation), we calculate the total moves required. The number of moves to transfer one stone from
(r1, c1)to(r2, c2)is the Manhattan distance:|r1 - r2| + |c1 - c2|. We sum these distances for all pairs in the current assignment. -
Find Minimum: We keep track of the minimum total moves found across all permutations. After checking all permutations, this minimum value is the solution.
import java.util.ArrayList; import java.util.Collections;import java.util.List; class Solution { private List<int[]> excessStones = new ArrayList<>(); private List<int[]> emptyCells = new ArrayList<>(); private int minMoves = Integer.MAX_VALUE; public int minimumMoves(int[][] grid) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (grid[i][j] > 1) { for (int k = 0; k < grid[i][j] - 1; k++) { excessStones.add(new int[]{i, j}); } } else if (grid[i][j] == 0) { emptyCells.add(new int[]{i, j}); } } } if (excessStones.isEmpty()) { return 0; } permute(0); return minMoves; } private void permute(int start) { if (start == emptyCells.size()) { int currentMoves = 0; for (int i = 0; i < excessStones.size(); i++) { currentMoves += Math.abs(excessStones.get(i)[0] - emptyCells.get(i)[0]) + Math.abs(excessStones.get(i)[1] - emptyCells.get(i)[1]); } minMoves = Math.min(minMoves, currentMoves); return; } for (int i = start; i < emptyCells.size(); i++) { Collections.swap(emptyCells, start, i); permute(start + 1); Collections.swap(emptyCells, start, i); // backtrack } }}Complexity
Time
O(k! * k), where k is the number of empty cells. The algorithm generates k! permutations of the `emptyCells` list. For each permutation, it takes O(k) time to calculate the total Manhattan distance. Given that k is at most 8, this is computationally feasible.
Space
O(k), where k is the number of empty cells. This space is used to store the `excessStones` and `emptyCells` lists, as well as for the recursion stack during permutation generation.
Trade-offs
Pros
Conceptually straightforward and relatively easy to implement.
Guaranteed to find the optimal solution because it exhaustively checks every possibility.
Cons
The factorial time complexity
O(k!)makes this approach impractical for slightly larger grids or more items to match.It is less efficient than dynamic programming, even for the small constraints of this problem.
Solutions
Solution
class Solution {public int minimumMoves(int[][] grid) { Deque<String> q = new ArrayDeque<>(); q.add(f(grid)); Set<String> vis = new HashSet<>(); vis.add(f(grid)); int[] dirs = {-1, 0, 1, 0, -1}; for (int ans = 0;; ++ans) { for (int k = q.size(); k > 0; --k) { String p = q.poll(); if ("111111111".equals(p)) { return ans; } int[][] cur = g(p); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { if (cur[i][j] > 1) { for (int d = 0; d < 4; ++d) { int x = i + dirs[d]; int y = j + dirs[d + 1]; if (x >= 0 && x < 3 && y >= 0 && y < 3 && cur[x][y] < 2) { int[][] nxt = new int[3][3]; for (int r = 0; r < 3; ++r) { for (int c = 0; c < 3; ++c) { nxt[r][c] = cur[r][c]; } } nxt[i][j]--; nxt[x][y]++; String s = f(nxt); if (!vis.contains(s)) { vis.add(s); q.add(s); } } } } } } } } }private String f(int[][] grid) { StringBuilder sb = new StringBuilder(); for (int[] row : grid) { for (int x : row) { sb.append(x); } } return sb.toString(); }private int[][] g(String s) { int[][] grid = new int[3][3]; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { grid[i][j] = s.charAt(i * 3 + j) - '0'; } } return grid; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.