Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A single straight cut must lie between two rows or between two columns. If one side has sum prefix, the other has sum total - prefix, so their equality can be checked from one running sum.

Approach

Compute the total of all grid values. Scan rows from top to bottom, adding an entire row before testing whether the accumulated sum equals the remaining sum. If any horizontal boundary succeeds, return true. Repeat column by column for vertical boundaries. Return false if neither direction succeeds.

Whole-row and whole-column accumulation enumerates exactly the possible straight cuts. Each side of a proper cut is a rectangle and therefore connected. The supplied Python loop also tests after the final row or column, but strictly positive values prevent that whole-grid-versus-empty comparison from succeeding, so it cannot produce an invalid answer.

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

        total = sum(grid[i][j] for j in range(m) for i in range(n))
        
        curr = 0
        for i in range(n):
            for j in range(m): curr += grid[i][j]
            if total - curr == curr: return True
        
        curr = 0
        for j in range(m):
            for i in range(n): curr += grid[i][j]
            if total - curr == curr: return True
        
        return False

Complexity analysis

Let r and c be the grid dimensions. Computing the total and scanning complete row and column prefixes takes O(rc) time and O(1) auxiliary space. Positivity makes the Python checks after the final row or column harmless, because an empty opposite side cannot have equal sum.