Minimum Moves to Spread Stones Over Grid solution and explanation
Google
9 more videos on this problem
Leetcode Weekly contest 362 - Medium - Minimum Moves to Spread Stones Over GridPrakhar Agrawal · 15:01 · 6K views
🔴 2850. Minimum Moves to Spread Stones Over Grid II Math II Recursion II BacktrackingAryan Mittal · 30:53 · 5K views
2850. Minimum Moves to Spread Stones Over Grid (Leetcode Medium)Programming Live with Larry · 12:43 · 2K views
2850. Minimum Moves to Spread Stones Over Grid || Combinations ✅ || Back Tracking 🔥Ayush Rao · 10:09 · 2K views
2850. Minimum Moves to Spread Stones Over Grid | With Harder Follow-up | Weekly Leetcode 362codingMohan · 30:52 · 1K views
Minimum Moves to Spread Stones Over Grid - LEETCODE WEEKLY CONTEST 362 (Explanation in details)Joyjit Codes · 4:58 · 1K views
【每日一题】LeetCode 2850. Minimum Moves to Spread Stones Over GridHuifeng Guan · 9:49 · 854 views
100030. Minimum Moves to Spread Stones Over Grid LeetCode Weekly Contest #leetcode #contestContest Codes · 0:36 · 615 views
Weekly Contest 362 || 2850. Minimum Moves to Spread Stones Over Grid(Medium) || Easy ExplanationManas Kumar Panda · 12:30 · 285 views
Leetcode 2850. Minimum Moves to Spread Stones Over Grid (permutation)LetsCode · 10:52 · 179 views
The 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.
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.
from collections import deque
def minMoves(grid):
def index(x, y):
return x * 3 + y
target = [1] * 9
current = [grid[i // 3][i % 3] for i in range(9)]
queue = deque([(current, 0)])
visited = set(tuple(current))
while queue:
state, moves = queue.popleft()
if state == target:
return moves
for i, stones in enumerate(state):
if stones > 1:
x, y = divmod(i, 3)
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < 3 and 0 <= ny < 3:
new_state = state[:]
new_state[i] -= 1
new_state[index(nx, ny)] += 1
new_state_tuple = tuple(new_state)
if new_state_tuple not in visited:
visited.add(new_state_tuple)
queue.append((new_state, moves + 1))
return -1The 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.
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.
public class Solution {
private int minMoves = Integer.MAX_VALUE;
public int minMoves(int[][] grid) {
int[] target = new int[9];
for (int i = 0; i < 9; i++) target[i] = 1;
dfs(grid, 0);
return minMoves;
}
private void dfs(int[][] grid, int moves) {
if (isTarget(grid)) {
minMoves = Math.min(minMoves, moves);
return;
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (grid[i][j] > 1) {
// try to move stones from (i, j) to adjacent cells
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (Math.abs(di) + Math.abs(dj) != 1) continue;
int ni = i + di, nj = j + dj;
if (ni >= 0 && ni < 3 && nj >= 0 && nj < 3) {
grid[i][j]--;
grid[ni][nj]++;
dfs(grid, moves + 1);
grid[i][j]++;
grid[ni][nj]--;
}
}
}
}
}
}
}
private boolean isTarget(int[][] grid) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (grid[i][j] != 1) return false;
}
}
return true;
}
}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.
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.
def min_moves(grid):
moves = 0
# Adjust horizontally
for r in range(3):
for c in range(2):
excess = grid[r][c] - 1
grid[r][c] -= excess
grid[r][c + 1] += excess
moves += abs(excess)
# Adjust vertically
for c in range(3):
for r in range(2):
excess = grid[r][c] - 1
grid[r][c] -= excess
grid[r + 1][c] += excess
moves += abs(excess)
return moves
grid = [[1,3,0],[1,0,0],[1,0,3]]
print(min_moves(grid)) # Output: 4public class MinMoves {
public int minMoves(int[][] grid) {
int moves = 0;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 2; c++) {
int excess = grid[r][c] - 1;
grid[r][c] -= excess;
grid[r][c + 1] += excess;
moves += Math.abs(excess);
}
}
for (int c = 0; c < 3; c++) {
for (int r = 0; r < 2; r++) {
int excess = grid[r][c] - 1;
grid[r][c] -= excess;
grid[r + 1][c] += excess;
moves += Math.abs(excess);
}
}
return moves;
}
public static void main(String[] args) {
MinMoves mm = new MinMoves();
int[][] grid = {{1, 3, 0}, {1, 0, 0}, {1, 0, 3}};
System.out.println(mm.minMoves(grid)); // Output: 4
}
}#include <iostream>
#include <cmath>
class MinMoves {
public:
int minMoves(int grid[3][3]) {
int moves = 0;
for (int r = 0; r < 3; ++r) {
for (int c = 0; c < 2; ++c) {
int excess = grid[r][c] - 1;
grid[r][c] -= excess;
grid[r][c + 1] += excess;
moves += std::abs(excess);
}
}
for (int c = 0; c < 3; ++c) {
for (int r = 0; r < 2; ++r) {
int excess = grid[r][c] - 1;
grid[r][c] -= excess;
grid[r + 1][c] += excess;
moves += std::abs(excess);
}
}
return moves;
}
};
int main() {
MinMoves mm;
int grid[3][3] = {{1, 3, 0}, {1, 0, 0}, {1, 0, 3}};
std::cout << mm.minMoves(grid) << std::endl; // Output: 4
return 0;
}function minMoves(grid) {
let moves = 0;
for (let r = 0; r < 3; r++) {
for (let c = 0; c < 2; c++) {
let excess = grid[r][c] - 1;
grid[r][c] -= excess;
grid[r][c + 1] += excess;
moves += Math.abs(excess);
}
}
for (let c = 0; c < 3; c++) {
for (let r = 0; r < 2; r++) {
let excess = grid[r][c] - 1;
grid[r][c] -= excess;
grid[r + 1][c] += excess;
moves += Math.abs(excess);
}
}
return moves;
}
const grid = [[1, 3, 0], [1, 0, 0], [1, 0, 3]];
console.log(minMoves(grid)); // Output: 4#include <stdio.h>
#include <stdlib.h>
int minMoves(int grid[3][3]) {
int moves = 0;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 2; c++) {
int excess = grid[r][c] - 1;
grid[r][c] -= excess;
grid[r][c + 1] += excess;
moves += abs(excess);
}
}
for (int c = 0; c < 3; c++) {
for (int r = 0; r < 2; r++) {
int excess = grid[r][c] - 1;
grid[r][c] -= excess;
grid[r + 1][c] += excess;
moves += abs(excess);
}
}
return moves;
}
int main() {
int grid[3][3] = {{1, 3, 0}, {1, 0, 0}, {1, 0, 3}};
printf("%d\n", minMoves(grid)); // Output: 4
return 0;
}using System;
public class MinMoves {
public int MinMoves(int[,] grid) {
int moves = 0;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 2; c++) {
int excess = grid[r, c] - 1;
grid[r, c] -= excess;
grid[r, c + 1] += excess;
moves += Math.Abs(excess);
}
}
for (int c = 0; c < 3; c++) {
for (int r = 0; r < 2; r++) {
int excess = grid[r, c] - 1;
grid[r, c] -= excess;
grid[r + 1, c] += excess;
moves += Math.Abs(excess);
}
}
return moves;
}
public static void Main(string[] args) {
MinMoves mm = new MinMoves();
int[,] grid = {{1, 3, 0}, {1, 0, 0}, {1, 0, 3}};
Console.WriteLine(mm.MinMoves(grid)); // Output: 4
}
}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.
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.
from collections import deque
def state_to_string(grid):
return ''.join(str(num) for row in grid for num in row)
def min_moves_bfs(grid):
init_state = tuple(tuple(row) for row in grid)
target = ((1, 1, 1), (1, 1, 1), (1, 1, 1))
queue = deque([(init_state, 0)]) # (state, depth)
seen = {state_to_string(init_state)}
while queue:
state, depth = queue.popleft()
if state == target:
return depth
for r in range(3):
for c in range(3):
if state[r][c] > 1:
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < 3 and 0 <= nc < 3:
new_state = [list(row) for row in state]
new_state[r][c] -= 1
new_state[nr][nc] += 1
new_state_tuple = tuple(tuple(row) for row in new_state)
new_state_str = state_to_string(new_state)
if new_state_str not in seen:
seen.add(new_state_str)
queue.append((new_state_tuple, depth + 1))
return -1
grid = [[1,3,0],[1,0,0],[1,0,3]]
print(min_moves_bfs(grid)) # Output: 4The 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.
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.
function minimumMoves(grid: number[][]): number {
const q: string[] = [f(grid)];
const vis: Set<string> = new Set([f(grid)]);
const dirs: number[] = [-1, 0, 1, 0, -1];
for (let ans = 0; ; ans++) {
let sz = q.length;
while (sz-- > 0) {
const p = q.shift()!;
if (p === '111111111') {
return ans;
}
const cur = g(p);
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (cur[i][j] > 1) {
for (let d = 0; d < 4; d++) {
const x = i + dirs[d],
y = j + dirs[d + 1];
if (x >= 0 && x < 3 && y >= 0 && y < 3 && cur[x][y] < 2) {
const nxt = cur.map(row => [...row]);
nxt[i][j]--;
nxt[x][y]++;
const s = f(nxt);
if (!vis.has(s)) {
vis.add(s);
q.push(s);
}
}
}
}
}
}
}
}
}
function f(grid: number[][]): string {
return grid.flat().join('');
}
function g(s: string): number[][] {
return Array.from({ length: 3 }, (_, i) =>
Array.from({ length: 3 }, (_, j) => Number(s[i * 3 + j])),
);
}type Queue []string
func (q *Queue) Push(s string) {
*q = append(*q, s)
}
func (q *Queue) Pop() string {
s := (*q)[0]
*q = (*q)[1:]
return s
}
func (q *Queue) Empty() bool {
return len(*q) == 0
}
func minimumMoves(grid [][]int) int {
q := Queue{f(grid)}
vis := map[string]bool{f(grid): true}
dirs := []int{-1, 0, 1, 0, -1}
for ans := 0; ; ans++ {
sz := len(q)
for ; sz > 0; sz-- {
p := q.Pop()
if p == "111111111" {
return ans
}
cur := g(p)
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
if cur[i][j] > 1 {
for d := 0; d < 4; d++ {
x, y := i+dirs[d], j+dirs[d+1]
if x >= 0 && x < 3 && y >= 0 && y < 3 && cur[x][y] < 2 {
nxt := make([][]int, 3)
for r := range nxt {
nxt[r] = append([]int(nil), cur[r]...)
}
nxt[i][j]--
nxt[x][y]++
s := f(nxt)
if !vis[s] {
vis[s] = true
q.Push(s)
}
}
}
}
}
}
}
}
}
func f(grid [][]int) string {
var sb strings.Builder
for _, row := range grid {
for _, x := range row {
sb.WriteByte(byte(x) + '0')
}
}
return sb.String()
}
func g(s string) [][]int {
grid := make([][]int, 3)
for i := range grid {
grid[i] = make([]int, 3)
for j := 0; j < 3; j++ {
grid[i][j] = int(s[i*3+j] - '0')
}
}
return grid
}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.
function minimumMoves(grid: number[][]): number {
const left: number[][] = [];
const right: number[][] = [];
for (let i = 0; i < 3; ++i) {
for (let j = 0; j < 3; ++j) {
if (grid[i][j] === 0) {
left.push([i, j]);
} else {
for (let k = 1; k < grid[i][j]; ++k) {
right.push([i, j]);
}
}
}
}
const cal = (a: number[], b: number[]) => {
return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
};
const n = left.length;
const f: number[] = Array(1 << n).fill(1 << 30);
f[0] = 0;
for (let i = 0; i < 1 << n; ++i) {
let k = 0;
for (let j = 0; j < n; ++j) {
if ((i >> j) & 1) {
++k;
}
}
for (let j = 0; j < n; ++j) {
if ((i >> j) & 1) {
f[i] = Math.min(f[i], f[i ^ (1 << j)] + cal(left[k - 1], right[j]));
}
}
}
return f[(1 << n) - 1];
}func minimumMoves(grid [][]int) int {
left := [][2]int{}
right := [][2]int{}
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
if grid[i][j] == 0 {
left = append(left, [2]int{i, j})
} else {
for k := 1; k < grid[i][j]; k++ {
right = append(right, [2]int{i, j})
}
}
}
}
cal := func(a, b [2]int) int {
return abs(a[0]-b[0]) + abs(a[1]-b[1])
}
n := len(left)
f := make([]int, 1<<n)
f[0] = 0
for i := 1; i < 1<<n; i++ {
f[i] = 1 << 30
k := bits.OnesCount(uint(i))
for j := 0; j < n; j++ {
if i>>j&1 == 1 {
f[i] = min(f[i], f[i^(1<<j)]+cal(left[k-1], right[j]))
}
}
}
return f[(1<<n)-1]
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}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 | – |
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 |
Frequently asked questions
Is Minimum Moves to Spread Stones Over Grid easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 45%. The difficulty comes from recognizing that the grid is small enough to treat the task as an assignment problem between surplus stones and empty cells rather than simulating every possible movement.
Minimum Moves to Spread Stones Over Grid Python/Java solution
Python implementations often use BFS with a queue or DFS with recursion to try all assignments. Java solutions commonly implement the DFS backtracking strategy by storing coordinates of extra stones and empty cells and computing Manhattan distance for each pairing.
How to solve Minimum Moves to Spread Stones Over Grid in O(n)?
A true O(n) algorithm is difficult because the problem requires evaluating different assignments between extra stones and empty cells. However, you can approximate a fast solution by collecting extra and empty positions and greedily matching them based on Manhattan distance. Optimal solutions typically use DFS backtracking over permutations.
What is the best approach for Minimum Moves to Spread Stones Over Grid?
DFS with backtracking is the most reliable approach. First collect positions of extra stones and empty cells, then try all assignments between them while computing Manhattan distance costs. Since the grid is only 3x3, the number of extra stones is small (at most 6), making the O(k!) search feasible and easy to implement.
Is Minimum Moves to Spread Stones Over Grid asked at Google/Amazon/Meta?
Grid movement and redistribution problems appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact question may not always appear, similar problems involving BFS on grids, state exploration, and Manhattan distance matching are common in technical interviews.
What data structure is used in Minimum Moves to Spread Stones Over Grid?
Common implementations use arrays or lists to store positions of extra stones and empty cells. BFS solutions rely on queues and hash sets to track visited states, while DFS backtracking uses recursion and arrays to represent assignments.
What is the time complexity of Minimum Moves to Spread Stones Over Grid?
The DFS backtracking solution runs in O(k!) time where k is the number of extra stones that must be moved. Space complexity is O(k) for recursion and tracking assignments. BFS solutions may explore many grid states but still remain manageable because the grid has only 9 cells.