Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For each straight cut, either the two sums already match or one cell of the heavier side must equal their difference. Removing that cell must also preserve connectivity. In a rectangle with at least two rows and two columns, any single-cell removal stays connected; in a one-dimensional strip, only an endpoint can be removed safely.

Approach

Compute the total sum. A helper scans proper row-prefix regions, maintaining their sum and the first and last coordinates of each value encountered. If the prefix and remainder have equal sums, accept. Otherwise look for a prefix cell equal to 2 * prefixSum - total, the excess of that side. Positive cell values ensure only a genuinely heavier prefix can match.

For a two-dimensional prefix, any matching cell works. For a single row or column, use the stored extreme occurrence coordinates to check whether a matching cell is at an endpoint.

Run the helper on the grid and its reversed row order to consider deletion from either side. Transpose the grid and repeat both scans for vertical cuts. Return true if any orientation succeeds; otherwise return false.

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        def check(g):
            nn = len(g)
            mm = len(g[0])
            curr = 0
            seen = {} # seen[v] = [coords for first, coords for last]

            for i in range(nn - 1):
                for j in range(mm):
                    v = g[i][j]
                    curr += v
                    if v in seen:
                        seen[v][1] = (i, j)
                    else:
                        seen[v] = [(i, j), (i, j)]
                diff = total - curr - curr
                if diff == 0:
                    return True
                if -diff in seen:
                    fr, fc = seen[-diff][0]
                    lr, lc = seen[-diff][1]
                    if mm > 1 and i + 1 > 1:
                        return True # big grid, always connected
                    if mm > 1 and i + 1 == 1 and (fc == 0 or lc == mm - 1):
                        return True # one row
                    if mm == 1 and (fr == 0 or lr == i):
                        return True # one col

        n = len(grid)
        m = len(grid[0])
        total = sum(grid[i][j] for j in range(m) for i in range(n))

        if check(grid) or check(grid[::-1]):
            return True

        # transpose grid
        # ng = []
        # for j in range(m):
        #     nr = []
        #     for i in range(n):
        #         nr.append(grid[i][j])
        #     ng.append(nr)
        grid = list(zip(*grid))

        if check(grid) or check(grid[::-1]):
            return True

        return False

Complexity analysis

Let r and c be the grid dimensions. Time: O(r * c). Auxiliary space: O(r * c) for value/coordinate maps and the transposed grid.