2850. Minimum Moves to Spread Stones Over Grid LeetCode Solution
In this guide, you will get 2850. Minimum Moves to Spread Stones Over Grid LeetCode Solution with the best time and space complexity. The solution to Minimum Moves to Spread Stones Over Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Moves to Spread Stones Over Grid
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.
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.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
2850. Minimum Moves to Spread Stones Over Grid LeetCode Solution in C++
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
const int zeroCount = accumulate(grid.begin(), grid.end(), 0,
[](int subtotal, const vector<int>& row) {
return subtotal + ranges::count(row, 0);
});
if (zeroCount == 0)
return 0;
int ans = INT_MAX;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
if (grid[i][j] == 0)
for (int x = 0; x < 3; ++x)
for (int y = 0; y < 3; ++y)
// Move a stone at (x, y) to (i, j).
if (grid[x][y] > 1) {
--grid[x][y];
++grid[i][j];
ans = min(ans, abs(x - i) + abs(y - j) + minimumMoves(grid));
++grid[x][y];
--grid[i][j];
}
return ans;
}
}; /* code provided by PROGIEZ */
2850. Minimum Moves to Spread Stones Over Grid LeetCode Solution in Java
class Solution {
public int minimumMoves(int[][] grid) {
int zeroCount = 0;
for (int[] row : grid)
for (int cell : row)
if (cell == 0)
++zeroCount;
if (zeroCount == 0)
return 0;
int ans = Integer.MAX_VALUE;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
if (grid[i][j] == 0)
for (int x = 0; x < 3; ++x)
for (int y = 0; y < 3; ++y)
if (grid[x][y] > 1) {
--grid[x][y];
++grid[i][j];
ans = Math.min(ans, Math.abs(x - i) + Math.abs(y - j) + minimumMoves(grid));
++grid[x][y];
--grid[i][j];
}
return ans;
}
} // code provided by PROGIEZ
2850. Minimum Moves to Spread Stones Over Grid LeetCode Solution in Python
class Solution:
def minimumMoves(self, grid: list[list[int]]) -> int:
if sum(row.count(0) for row in grid) == 0:
return 0
ans = math.inf
for i in range(3):
for j in range(3):
if grid[i][j] == 0:
for x in range(3):
for y in range(3):
if grid[x][y] > 1:
grid[x][y] -= 1
grid[i][j] += 1
ans = min(ans, abs(x - i) + abs(y - j) +
self.minimumMoves(grid))
grid[x][y] += 1
grid[i][j] -= 1
return ans # code by PROGIEZ
