LeetCode 3548 - Equal Sum Grid Partition II

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Matrix, Enumeration, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine if we can partition a given m x n grid of positive integers into two connected sections by making exactly one horizontal or vertical cut, such that the sums of the two sections are equal or can be made equal by removing at most one cell. A key requirement is that after removing a cell, the remaining cells in the section must remain connected.

The input is a 2D matrix of positive integers. The output is a boolean value, true if such a partition is possible and false otherwise.

The constraints indicate that the matrix can be large, with up to 100,000 cells in total, but each individual dimension could be large as well. This rules out any algorithm that checks every possible cut in a naive nested-loop manner. Important edge cases include very small grids (2x1, 1x2), grids where all numbers are equal, or grids where removing a cell may disconnect the section.

Approaches

The brute-force approach would enumerate all possible horizontal and vertical cuts. For each cut, compute the sums of both resulting sections. If the sums are not equal, we could try removing one cell from either section and check if the sums can be made equal while keeping the section connected. This requires checking connectivity, which itself can take O(mn) using BFS/DFS, and the number of candidate cells to remove is large. For large grids, this approach is computationally infeasible.

The key insight is that the problem can be reduced by using prefix sums along rows and columns. Since only one cut is allowed, we only need the total sums for potential top/bottom or left/right sections. To satisfy the "discount at most one cell" rule, we just need to check if the difference in sums is equal to any single cell in the other section. Connectivity checks become trivial because removing a single cell from a contiguous row or column section cannot split it if the section has more than one row or column. Therefore, the problem reduces to computing prefix sums and checking for simple differences.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n * (m + n))	O(1)	Compute sums for each cut and check all removable cells with connectivity
Optimal	O(m * n)	O(m + n)	Use row and column prefix sums, check single-cell discount conditions

Algorithm Walkthrough

Compute the total sum of the grid. This is needed to quickly calculate sums of sections after a cut.
Compute row-wise prefix sums. This allows us to get the sum of the top section for any horizontal cut in O(1) time.
Compute column-wise prefix sums. This allows us to get the sum of the left section for any vertical cut in O(1) time.
For horizontal cuts, iterate through rows from 1 to m-1. For each cut, calculate the top and bottom section sums using the row prefix sums. If the sums are equal, return true. If not, check if the difference between the sums is equal to any single cell in either section. If so, return true.
Repeat a similar process for vertical cuts using the column prefix sums. Iterate through columns from 1 to n-1 and check sums and single-cell discount possibilities.
If no valid cut is found after checking all possibilities, return false.

Why it works: By using prefix sums, we efficiently compute section sums. Checking the difference against individual cells captures the "discount one cell" rule. Sections remain connected since removing a single cell from a contiguous row or column does not split the section.

Python Solution

from typing import List

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

        # Compute row and column prefix sums
        row_sums = [sum(row) for row in grid]
        col_sums = [sum(grid[i][j] for i in range(m)) for j in range(n)]

        # Horizontal cuts
        top_sum = 0
        for i in range(m - 1):
            top_sum += row_sums[i]
            bottom_sum = total_sum - top_sum
            if top_sum == bottom_sum:
                return True
            diff = abs(top_sum - bottom_sum)
            # Check if any cell in top or bottom can fix the difference
            if any(diff == grid[r][c] for r in range(i + 1) for c in range(n)):
                return True
            if any(diff == grid[r][c] for r in range(i + 1, m) for c in range(n)):
                return True

        # Vertical cuts
        left_sum = 0
        for j in range(n - 1):
            left_sum += col_sums[j]
            right_sum = total_sum - left_sum
            if left_sum == right_sum:
                return True
            diff = abs(left_sum - right_sum)
            # Check if any cell in left or right can fix the difference
            if any(diff == grid[r][c] for r in range(m) for c in range(j + 1)):
                return True
            if any(diff == grid[r][c] for r in range(m) for c in range(j + 1, n)):
                return True

        return False

Explanation: We first calculate the total sum and prefix sums. We iterate over potential horizontal and vertical cuts, calculate the sums of resulting sections, and check if they are equal. If not, we see if removing a single cell can make them equal.

Go Solution

func canPartitionGrid(grid [][]int) bool {
    m, n := len(grid), len(grid[0])
    totalSum := 0
    rowSums := make([]int, m)
    colSums := make([]int, n)

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            val := grid[i][j]
            totalSum += val
            rowSums[i] += val
            colSums[j] += val
        }
    }

    topSum := 0
    for i := 0; i < m-1; i++ {
        topSum += rowSums[i]
        bottomSum := totalSum - topSum
        if topSum == bottomSum {
            return true
        }
        diff := topSum - bottomSum
        if diff < 0 {
            diff = -diff
        }
        // Check horizontal single cell discount
        for r := 0; r <= i; r++ {
            for c := 0; c < n; c++ {
                if grid[r][c] == diff {
                    return true
                }
            }
        }
        for r := i + 1; r < m; r++ {
            for c := 0; c < n; c++ {
                if grid[r][c] == diff {
                    return true
                }
            }
        }
    }

    leftSum := 0
    for j := 0; j < n-1; j++ {
        leftSum += colSums[j]
        rightSum := totalSum - leftSum
        if leftSum == rightSum {
            return true
        }
        diff := leftSum - rightSum
        if diff < 0 {
            diff = -diff
        }
        // Check vertical single cell discount
        for r := 0; r < m; r++ {
            for c := 0; c <= j; c++ {
                if grid[r][c] == diff {
                    return true
                }
            }
        }
        for r := 0; r < m; r++ {
            for c := j + 1; c < n; c++ {
                if grid[r][c] == diff {
                    return true
                }
            }
        }
    }

    return false
}

Explanation: Go implementation mirrors Python. Differences include explicit handling of slices and using standard for loops for sums. The absolute value of differences is computed manually. Connectivity is implicitly preserved by the single-cell discount assumption.

Worked Examples

Example 1: `grid = [[1,4],[2,3]]`

Horizontal cut after row 0:

Section	Sum
Top	1+4=5
Bottom	2+3=5

Sums equal, return true.

Example 2: `grid = [[1,2],[3,4]]`

Vertical cut after column 0:

Section	Sum
Left	1+3=4
Right	2+4=6

Difference = 2, check if any cell in the right section is 2 → found (2), return true.

Example 3: `grid = [[1,2,4],[2,3,5]]`