Minimum Moves to Spread Stones Over Grid

Hard
924.

Minimum Moves to Spread Stones Over Grid

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.

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 == 3
  • 0 <= grid[i][j] <= 9
  • The sum of grid is 9.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumMoves = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 == 3
  • 0 <= grid[i][j] <= 9
  • The sum of grid is 9.

Hints for Minimum Moves to Spread Stones Over Grid

  1. Hint 1

    Break the problem into single stones: a cell holding c > 1 has c - 1 spare stones, and a cell holding 0 needs one.

  2. Hint 2

    Moving one stone from (a,b) to (x,y) costs the Manhattan distance, since nothing blocks the way.

  3. 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

  1. Build from, one entry per spare stone (a cell with c stones contributes c - 1).
  2. Build to, one entry per empty cell. The two lists have the same length because the grid sums to 9.
  3. Try every way to assign spares to holes, summing Manhattan distances, and keep the cheapest.
  4. 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 c stones has c - 1 spares, not c.
  • 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