Minimum Moves to Spread Stones Over Grid - Practice Coding Problems

Minimum Moves to Spread Stones Over Grid - Problem

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 (adjacent horizontally or vertically).

Return the minimum number of moves required to place one stone in each cell.

Input & Output

Example 1 — Uneven Distribution

$ Input: grid = [[1,1,0],[1,1,1],[1,1,1]]

› Output: 3

💡 Note: One stone needs to move from (1,1) to (0,2) costing 3 moves. Two stones can move from nearby positions to reach the empty cell optimally.

Example 2 — Already Balanced

$ Input: grid = [[1,1,1],[1,1,1],[1,1,1]]

› Output: 0

💡 Note: Grid already has exactly one stone in each cell, so no moves are needed.

Example 3 — Corner Case

$ Input: grid = [[3,2,2],[0,1,1],[0,1,1]]

› Output: 4

💡 Note: Need to move 2 stones from (0,0) and 1 stone each from (0,1) and (0,2) to empty corners. Minimum total Manhattan distance is 4.

Constraints

grid.length == 3
grid[i].length == 3
0 ≤ grid[i][j] ≤ 9
Sum of grid[i][j] == 9

Visualization

Tap to expand

Understanding the Visualization

Input

3×3 grid with 9 stones unevenly distributed

Process

Move stones to achieve exactly 1 stone per cell

Output

Minimum number of moves required

Key Takeaway

🎯 Key Insight: Model as assignment problem - find optimal mapping of excess stones to empty cells using Manhattan distance

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to model this as an assignment problem where excess stones must be optimally assigned to empty cells. Since the grid is small (3×3), we can try all possible assignments and calculate Manhattan distances. Best approach uses backtracking with pruning to reduce search space while guaranteeing optimal solution. Time: O(k!), Space: O(k) where k is number of excess stones.

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Pruning	O(k!)	O(k)	Use backtracking with early termination when current cost exceeds best found
Brute Force Assignment	O(k!)	O(k)	Try all possible assignments of excess stones to empty cells

Backtracking with Pruning — Algorithm Steps

Step 1: Collect excess stones and empty positions
Step 2: Use recursive backtracking to try assignments
Step 3: Prune branches when current cost ≥ best solution
Step 4: Return minimum cost found

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Best

Keep track of best solution found so far

Prune Early

Stop exploring when current cost ≥ best cost

Optimize

Significantly reduce search space through pruning

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
    int r, c;
} Position;

int bestCost = INT_MAX;

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int backtrack(Position* excess, Position* empty, int excessCount, int emptyCount, int idx, int currentCost, int* used) {
    if (idx == excessCount) return currentCost;
    
    if (currentCost >= bestCost) return INT_MAX; // Prune
    
    int minCost = INT_MAX;
    for (int i = 0; i < emptyCount; i++) {
        if (!used[i]) {
            int cost = abs_val(excess[idx].r - empty[i].r) + abs_val(excess[idx].c - empty[i].c);
            used[i] = 1;
            int result = backtrack(excess, empty, excessCount, emptyCount, idx + 1, currentCost + cost, used);
            if (result < bestCost) bestCost = result;
            if (result < minCost) minCost = result;
            used[i] = 0;
        }
    }
    return minCost;
}

int solution(int grid[3][3]) {
    Position excess[9], empty[9];
    int excessCount = 0, emptyCount = 0;
    
    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++) {
                    excess[excessCount].r = i;
                    excess[excessCount].c = j;
                    excessCount++;
                }
            } else if (grid[i][j] == 0) {
                empty[emptyCount].r = i;
                empty[emptyCount].c = j;
                emptyCount++;
            }
        }
    }
    
    bestCost = INT_MAX;
    int used[9] = {0};
    return backtrack(excess, empty, excessCount, emptyCount, 0, 0, used);
}

int main() {
    char line[100];
    fgets(line, sizeof(line), stdin);
    
    int grid[3][3];
    char* ptr = line + 1; // skip first '['
    for (int i = 0; i < 3; i++) {
        ptr++; // skip '['
        for (int j = 0; j < 3; j++) {
            grid[i][j] = strtol(ptr, &ptr, 10);
            if (*ptr == ',') ptr++;
        }
        ptr++; // skip ']'
        if (*ptr == ',') ptr++;
    }
    
    printf("%d\n", solution(grid));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k!)

Still k! in worst case but pruning reduces average case significantly

✓ Linear Growth

Space Complexity

O(k)

Recursion stack depth k, plus arrays for excess/empty positions

✓ Linear Space

17.9K Views

Medium Frequency

~25 min Avg. Time

687 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler