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.

Return true if such a partition exists, otherwise return false.

Approach

To solve this problem, we can use prefix sums to efficiently calculate the sum of any subgrid. We will calculate the cumulative sums for both rows and columns.

Then, we will check if there exists a partition (either horizontal or vertical) where the sum of one part equals the sum of the other part. This will make use of suffix sums as well, to compare the sums of the two parts without having to recalculate them from scratch.

Solution in Python


class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        M = len(grid)
        N = len(grid[0])

        # cumulative sum of each column
        colSums = [0 for _ in range(N)]

        # cumulative sum of each row
        rowSums = [0 for _ in range(M)]

        # col prefix sum calculation
        for i in range(M):
            for j in range(N):
                colSums[j] += grid[i][j]
                rowSums[i] += grid[i][j]

        colPrefixSum = [0 for _ in range(N)]
        colSuffixSum = [0 for _ in range(N)]

        colPrefixSum[0] = colSums[0]
        colSuffixSum[-1] = colSums[-1]
        
        # cumulative col prefix sum
        for j in range(1, N):
            colPrefixSum[j] += colPrefixSum[j - 1] + colSums[j]
        
        # cumulative col suffix sum
        for j in reversed(range(N - 1)):
            colSuffixSum[j] += colSuffixSum[j + 1] + colSums[j]

        # cumulative row prefix sum
        rowPrefixSum = [0 for _ in range(M)]
        rowSuffixSum = [0 for _ in range(M)]

        rowPrefixSum[0] = rowSums[0]
        rowSuffixSum[-1] = rowSums[-1]
        
        # cumulative row prefix sum
        for i in range(1, M):
            rowPrefixSum[i] += rowPrefixSum[i - 1] + rowSums[i]
        
        # cumulative row suffix sum
        for i in reversed(range(M - 1)):
            rowSuffixSum[i] += rowSuffixSum[i + 1] + rowSums[i]

        # now check if row prefix sum at prev index = row suffix sum at next index
        for i in range(M - 1):
            if rowPrefixSum[i] == rowSuffixSum[i + 1]:
                return True
        
        # now check if col prefix sum at prev index = col suffix sum at next index
        for j in range(N - 1):
            if colPrefixSum[j] == colSuffixSum[j + 1]:
                return True
        
        return False

Complexity

  • Time: $O(M \times N)$
    Since we traverse the grid to calculate cumulative sums and then check for valid partitions.

  • Space: $O(M + N)$
    Since we store the cumulative sums of rows and columns.

And we are done.