Minimum Moves to Spread Stones Over Grid — Solution
Minimum Moves to Spread Stones Over Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Moves to Spread Stones Over Grid is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Zomato interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix, Breadth-First Search
- Asked at: Amazon, Google, Zomato
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A 3 × 3 grid holds nine stones in total, but some cells may hold several and some none. In one move you may take one stone from a cell and move it to an adjacent cell — up, down, left or right.
Return the minimum number of moves needed to leave exactly one stone in every cell.
Example 1
Input: grid = [[1,1,0],[1,1,1],[1,2,1]]
Output: 3
Explanation: Walk a stone from `(2,1)` up and left to the empty `(0,2)`.
Example 2
Input: grid = [[1,3,0],[1,0,0],[1,0,3]]
Output: 4
Example 3
Input: grid = [[1,1,1],[1,1,1],[1,1,1]]
Output: 0
Constraints
grid.length == grid[i].length == 30 <= grid[i][j] <= 9The sum of grid is 9.
Hints for Minimum Moves to Spread Stones Over Grid
Hint 1
Break the problem into single stones: a cell holding
c > 1hasc - 1spare stones, and a cell holding 0 needs one.Hint 2
Moving one stone from
(a,b)to(x,y)costs the Manhattan distance, since nothing blocks the way.Hint 3
So the answer is the cheapest way to pair up the spares with the holes — at most 8 of each.
How to solve Minimum Moves to Spread Stones Over Grid
Reduce to an assignment problem. Each surplus stone must end in some empty cell, the cost of a pairing is the Manhattan distance, and the answer is the minimum-cost perfect matching between the two equal-sized lists.
Approach
- Build
from, one entry per spare stone (a cell withcstones contributesc - 1). - Build
to, one entry per empty cell. The two lists have the same length because the grid sums to 9. - Try every way to assign spares to holes, summing Manhattan distances, and keep the cheapest.
- Prune a branch as soon as its partial cost reaches the best found.
Why it works
A stone can always travel along a shortest Manhattan route — the other stones never block it, since a cell may hold any number on the way — so the cost of a pairing really is the sum of distances, and no cleverer routing exists. Both lists have at most 8 entries, so 8! = 40 320 assignments is trivially searchable; bitmask DP over the holes is the O(2^k · k) refinement.
Complexity
- Time —
O(k!) with pruning, k <= 8 — or O(2^k · k) with bitmask DP - Space —
O(k)
Pitfalls
- A cell with
cstones hasc - 1spares, notc. - Stones do not obstruct each other, so the cost is plain Manhattan distance — no BFS needed.
- An already-correct grid answers 0; the search must handle both lists being empty.
Reference solution
Python
from typing import List
def minimumMoves(grid: List[List[int]]) -> int:
src, dst = [], []
for i in range(3):
for j in range(3):
if grid[i][j] > 1:
src.extend([(i, j)] * (grid[i][j] - 1))
elif grid[i][j] == 0:
dst.append((i, j))
k = len(src)
used = [False] * k
best = [float('inf')]
def walk(idx: int, cost: int) -> None:
if cost >= best[0]:
return
if idx == k:
best[0] = cost
return
for t in range(k):
if used[t]:
continue
used[t] = True
walk(idx + 1, cost + abs(src[t][0] - dst[idx][0]) + abs(src[t][1] - dst[idx][1]))
used[t] = False
walk(0, 0)
return 0 if best[0] == float('inf') else best[0]Java
public static int minimumMoves(int[][] grid) {
List<int[]> from = new ArrayList<>(), to = new ArrayList<>();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (grid[i][j] > 1) {
for (int k = 1; k < grid[i][j]; k++) from.add(new int[] { i, j });
} else if (grid[i][j] == 0) {
to.add(new int[] { i, j });
}
}
}
int k = from.size();
if (k == 0) return 0;
int full = 1 << k;
int[] dp = new int[full];
Arrays.fill(dp, Integer.MAX_VALUE / 2);
dp[0] = 0;
for (int mask = 0; mask < full; mask++) {
int idx = Integer.bitCount(mask);
if (idx == k || dp[mask] >= Integer.MAX_VALUE / 2) continue;
for (int t = 0; t < k; t++) {
if ((mask & (1 << t)) != 0) continue;
int cost = Math.abs(from.get(t)[0] - to.get(idx)[0]) + Math.abs(from.get(t)[1] - to.get(idx)[1]);
dp[mask | (1 << t)] = Math.min(dp[mask | (1 << t)], dp[mask] + cost);
}
}
return dp[full - 1];
}C++
int minimumMoves(vector<vector<int>>& grid) {
vector<pair<int,int>> from, to;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (grid[i][j] > 1) {
for (int k = 1; k < grid[i][j]; k++) from.push_back({ i, j });
} else if (grid[i][j] == 0) {
to.push_back({ i, j });
}
}
}
int k = (int) from.size();
if (k == 0) return 0;
int full = 1 << k;
vector<int> dp(full, 1 << 29);
dp[0] = 0;
for (int mask = 0; mask < full; mask++) {
if (dp[mask] >= (1 << 29)) continue;
int idx = __builtin_popcount(mask);
if (idx == k) continue;
for (int t = 0; t < k; t++) {
if (mask & (1 << t)) continue;
int cost = abs(from[t].first - to[idx].first) + abs(from[t].second - to[idx].second);
dp[mask | (1 << t)] = min(dp[mask | (1 << t)], dp[mask] + cost);
}
}
return dp[full - 1];
}JavaScript
var minimumMoves = function(grid) {
var from = [], to = [], i, j, kk;
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if (grid[i][j] > 1) {
for (kk = 1; kk < grid[i][j]; kk++) from.push([i, j]);
} else if (grid[i][j] === 0) {
to.push([i, j]);
}
}
}
var k = from.length;
var used = [];
for (i = 0; i < k; i++) used.push(false);
var best = Infinity;
var walk = function(idx, cost) {
if (cost >= best) return;
if (idx === k) { best = cost; return; }
for (var t = 0; t < k; t++) {
if (used[t]) continue;
used[t] = true;
walk(idx + 1, cost + Math.abs(from[t][0] - to[idx][0]) + Math.abs(from[t][1] - to[idx][1]));
used[t] = false;
}
};
walk(0, 0);
return best === Infinity ? 0 : best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming