Problem Statement in English

You’re given a 2D grid of integers. You have to determine if it’s possible to partition the grid into two non-empty parts such that the sum of the integers in both parts is equal. The partition can be made either horizontally or vertically.

Further, if removing a single cell from either part can make the sums equal, then the partition is also considered valid. However, upon removing a cell, the partition must still be connected, meaning that all remaining cells in each part must be adjacent to at least one other cell in the same part.

Approach

The way you implement this determines how easy it seems.

The idea here is that we initially assign the entire grid to the bottom parition and then row by row we move the rows to the top partition. After moving each row, we check if the sums of the two partitions are equal. If they are, we can return true immediately. If not, we check if the difference between the sums of the two partitions is equal to any of the elements in either partition. If it is, we can return true immediately as well.

But this only considers the horizontal partition. We also need to consider the vertical partition. We can do this by transposing the grid and applying the same logic as above. Reuse, reduce…rejoice :)

The connection condition is actually pretty easy to satisfy. If the cell we’re removing is in a partition whose height is just 1, then the cell to remove can only from either end, otherwise it would disconnect the partition. If the cell we’re removing is in a partition whose height is more than 1, then we can remove any cell without disconnecting the partition.

And we’re done!

Solution in Python


class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        def solve(grid):
            bottomFreq, bottomSum = defaultdict(int), 0
            topFreq, topSum = defaultdict(int), 0

            M, N = len(grid), len(grid[0])

            for i in range(M):
                for j in range(N):
                    v = grid[i][j]

                    bottomFreq[v] += 1
                    bottomSum += v 

            for i in range(M - 1):
                for j in range(N):
                    v = grid[i][j]

                    topFreq[v] += 1
                    topSum += v
                    
                    bottomFreq[v] -= 1
                    if not bottomFreq[v]: del bottomFreq[v]
                    bottomSum -= v

                diff_t = topSum - bottomSum
                if diff_t in topFreq:
                    if (i > 0 and N > 1) or diff_t in (grid[0][0], grid[i][N-1]):
                        return True

                diff_b = bottomSum - topSum
                if diff_b in bottomFreq:
                    if (i < M - 2 and N > 1) or diff_b in (grid[i+1][0], grid[M-1][N-1]):
                        return True

                if bottomSum == topSum: return True

            return False

        return solve(grid) or solve(list(zip(*grid)))

Complexity

  • Time: $O(M \times N)$
    Since we iterate through the grid once.

  • Space: $O(M \times N)$
    Since we store the frequency of all elements in the grid.

Mistakes I Made

I had to look this up :(

And we are done.