Quick Overview

Find the fewest orthogonal stone moves required to leave exactly one stone in every cell of a three-by-three grid.

Spread Nine Stones Across a Three-by-Three Grid with Minimum Moves

Company: American

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

A 3 by 3 grid contains exactly nine stones in total. A move takes one stone from a cell containing at least one stone and places it in a cell sharing an edge with that cell. Find the minimum number of moves needed so that every cell contains exactly one stone. ### Function Signature `minimum_stone_moves(grid: list[list[int]]) -> int` ### Rules - A move is one step up, down, left, or right within the grid; diagonal moves are not allowed. - A cell may temporarily contain more than one stone. - Every stone is identical, and each one-step move costs one. - The nine-stone total and orthogonal adjacency are explicit exercise assumptions making the target reachable. ### Constraints - `grid` has exactly three rows, each containing three integers. - `0 <= grid[r][c] <= 9`. - The sum of all entries is exactly 9. - Do not mutate the input grid. ### Examples Input: `grid = [[1,1,0],[1,1,1],[1,2,1]]` Output: `3` One surplus stone at row 2, column 1 must reach row 0, column 2, requiring three moves. Rows and columns are zero-based. Input: `grid = [[1,1,1],[1,1,1],[1,1,1]]` Output: `0` Input: `grid = [[9,0,0],[0,0,0],[0,0,0]]` Output: `18`

Overview: Find the fewest orthogonal stone moves required to leave exactly one stone in every cell of a three-by-three grid.

Read the full American Software Engineer interview experience this question came from

You are given a 3 by 3 grid of non-negative integers. `grid[r][c]` is the number of stones currently sitting in the cell at row `r`, column `c`; rows and columns are numbered from 0. The grid contains exactly nine stones in total. One move takes a single stone out of a cell that currently holds at least one stone and places it in a cell sharing an edge with that cell: one step up, down, left, or right, never diagonally and never off the grid. Every stone is identical and each one-step move costs one. A cell may temporarily hold more than one stone at any intermediate point. Return the minimum number of moves needed so that every one of the nine cells holds exactly one stone. Do not mutate the input grid. The nine-stone total and the orthogonal adjacency rule are assumptions of the exercise that make the target arrangement reachable. Output semantics: the answer is a single integer, the minimum total number of one-step moves. There is nothing to order or tie-break, because the return value is one number rather than an arrangement. The answer always fits in a 32-bit signed integer (it can never exceed 9 stones times the grid's Manhattan diameter of 4, i.e. 36), so Java returns `int` and C++ returns `int`; no 64-bit type is needed. Example 1: Input: `grid = [[1,1,0],[1,1,1],[1,2,1]]` Output: `3` Explanation: Cell (2,1) holds one extra stone and cell (0,2) is the only empty cell. That stone travels up, up, and right, which is |2 - 0| + |1 - 2| = 3 moves. No cheaper sequence exists. Example 2: Input: `grid = [[9,0,0],[0,0,0],[0,0,0]]` Output: `18` Explanation: Eight stones must leave (0,0), one for each of the eight empty cells. Their distances from (0,0) are 1, 2, 1, 2, 3, 2, 3, and 4, so the total is 18.

Constraints

  • `grid` has exactly three rows, each containing three integers.
  • `0 <= grid[r][c] <= 9`.
  • The sum of all nine entries is exactly 9.
  • A move is one step up, down, left, or right within the grid; diagonal moves are not allowed.
  • A cell may temporarily contain more than one stone, and every stone is identical with each one-step move costing one.
  • Do not mutate the input grid; the caller may reuse it after the call.
  • The returned count fits in a 32-bit signed integer (it never exceeds 36), so no 64-bit type is required.

Examples

Input: ([[1, 1, 1], [1, 1, 1], [1, 1, 1]],)

Expected Output: 0

Explanation: Minimum valid case: every cell already holds exactly one stone, so no cell is in surplus or deficit and zero moves are needed.

Input: ([[1, 1, 0], [1, 1, 1], [1, 2, 1]],)

Expected Output: 3

Explanation: Source example 1: the only extra stone sits at (2,1) and the only empty cell is (0,2); |2-0| + |1-2| = 3 moves.

Hints

  1. Every cell holding more than one stone has extras it must send away, and every empty cell must receive exactly one stone. Start by counting how many stones are in surplus and how many cells are empty, and convince yourself those two counts are always equal.
  2. Because steps are orthogonal and a cell may hold several stones along the way, one stone travelling from (r1,c1) to (r2,c2) costs exactly |r1 - r2| + |c1 - c2| moves, independent of every other stone.
  3. The number of surplus stones is small (at most eight). Ask whether sending a stone to the empty cell that happens to be closest to it can force a much more expensive trip for some other stone.

Loading coding console...

Show the approach

Approach

Reduction. Because a stone may pass through crowded cells freely and each step costs one, the cheapest way to move one stone from (r1,c1) to (r2,c2) is |r1-r2| + |c1-c2| steps, and independent stone paths never interfere. The final arrangement is fully determined (one stone per cell), so the task reduces to a transportation problem: expand every cell holding v > 1 into v - 1 surplus stones located at that cell, list every cell holding 0 as a deficit slot, and find the minimum-total-distance perfect matching between them under Manhattan cost. Any sequence of moves induces such an assignment with cost at least the matching's cost, and any assignment can be realised by walking each stone along a monotone path, so the minimum matching cost equals the minimum number of moves.

Invariant and sizes. Since the entries sum to 9 over nine cells, sum over cells of (v - 1) = 0, hence the number of surplus stones equals the number of empty cells; call it n. With nine stones, n is at most 8 (all nine in one cell gives 8 extras and 8 empty cells).

Algorithm. A bitmask DP over the deficit slots computes the optimal matching: dp[mask] is the cheapest cost of assigning the first popcount(mask) surplus stones (in scan order) to exactly the slots in mask. Because the stones are processed in a fixed order, popcount(mask) is the index of the next unassigned stone, so each state has a well-defined successor set; transitions add one unused slot j at cost |sr - dr_j| + |sc - dc_j|. dp[(1 << n) - 1] is the answer. Every permutation of slots is reachable, so the DP explores all n! matchings in 2^n * n work without enumerating them.

Why greedy fails. Assigning each surplus stone to its currently nearest empty cell can strand a later stone; on [[0,1,1],[1,2,1],[1,0,2]] that greedy costs 5 while the optimal matching costs 3. Independently matching each stone to its nearest empty cell without reserving it undercounts: on [[3,1,1],[1,1,1],[1,0,0]] both extras start at (0,0) and must fill two distinct cells, costing 7 rather than 6.

Edge cases. An already-balanced grid has n = 0; the code returns 0 before building any DP table, which also avoids indexing an empty table. A single cell holding all nine stones produces the maximum n = 8 (256 states). Cells holding exactly 1 are neither surplus nor deficit. The grid is only read, never written, so the caller may reuse the same list after the call. All arithmetic stays far inside 32-bit range: the answer is at most 36.

Time complexity:
O(2^n * n) where n <= 8 is the number of surplus stones, so O(1) for the fixed 3 by 3 grid (at most 2048 transitions).
Space complexity:
O(2^n) for the DP table plus O(n) for the surplus and deficit lists, i.e. O(1) for the fixed 3 by 3 grid.