Problem Statement in English

You’re given a 2D grid of size m x n where each cell contains a non-negative integer representing the number of stones in that cell. You can perform the following operation any number of times:

  • Choose a cell with at least one stone and move one stone from that cell to an adjacent cell (up, down, left, or right).

Your task is to determine the minimum number of moves required to spread all the stones in the grid such that no cell contains more than one stone. If it’s impossible to achieve this, return -1.

Approach

You can’t be greedy here. You have to try all possible combinations of moving the stones to the empty cells. This is because choosing a stone as donor may result in teh starvation of another that now has to get its stone from a farther cell.

You can use a recursive approach to try all combinations and keep track of the minimum moves required.

And we’re done!

Solution in Python


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        empty = []
        hm = defaultdict(int)
        M = len(grid)
        N = len(grid[0])

        for i in range(M):
            for j in range(N):
                if grid[i][j] == 0:
                    empty.append((i, j))
                elif grid[i][j] > 1:
                    hm[(i, j)] = grid[i][j]

        def cost(x1, y1, x2, y2):
            return abs(x1 - x2) + abs(y1 - y2)

        E = len(empty)
        res = inf

        def dfs(i, moves):
            if i >= E:
                nonlocal res
                res = min(res, moves)
                return

            for k, v in hm.items():
                if v == 1: continue

                hm[k] -= 1
                dfs(i + 1, moves + cost(k[0], k[1], empty[i][0], empty[i][1]))
                hm[k] += 1

        dfs(0, 0)

        return res

Complexity

  • Time: $O(8^8)$
    This is because we have at most 8 empty cells and for each cell we can choose from at most 8 donors.

  • Space: $O(8)$
    Since we have at most 8 empty cells and we are using a recursive approach, the maximum depth of the recursion will be 8.

Mistakes I Made

I went with the greedy approach :(

And we are done.