Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Minimum Moves to Spread Stones Over Grid

Explore how to apply backtracking to solve the problem of distributing stones so each cell in a 3x3 grid contains exactly one stone. Understand how to identify empty and extra stone cells, calculate move costs using Manhattan distance, and recursively explore all configurations to find the minimum moves required. This lesson guides learners in using a methodical approach to manage state and optimize moves within fixed constraints.

We'll cover the following...

Statement

Given a 2D grid of integers of size (3×33 \times 3), where each value represents the number of stones in the given cell, return the minimum number of moves required to place exactly one stone in each grid cell.

Constraints:

  • Only one stone can be moved in one move.

  • Stone from a cell can only be moved to another cell if they are adjacent (share a side).

  • The sum of all stones in the grid must be equal to 99.

  • grid.length, grid[i].length ...