Scale Engineer

Minimum Moves to Spread Stones Over Grid

Med
#2549Time: 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.2 companies
Patterns
Dynamic Programming
Algorithms
Breadth-First Search
Data structures
ArrayMatrix
Companies
GeicoGuidewire

Prompt

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

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 excessStones containing the coordinates of each extra stone. If a cell has g stones, its coordinate is added g-1 times.
  • Create a list emptyCells containing the coordinates of each empty cell.
  • Generate all possible permutations of the emptyCells list.
  • For each permutation, calculate the total cost by summing the Manhattan distances between the i-th stone in excessStones and the i-th cell in the permuted emptyCells list.
  • 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.

  1. 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 called excessStones exactly grid[i][j] - 1 times.
    • Cells with grid[i][j] == 0: These are empty cells that need a stone. We add their coordinates (i, j) to a list called emptyCells.

  2. Generate Permutations: The problem is now to match each stone in excessStones to a unique cell in emptyCells. We can solve this by trying every possible permutation of the emptyCells list. 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.

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

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

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.

← Previous

Previous problem

Next →

Next problem