LeetCode 3548 - Equal Sum Grid Partition II

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

Solution

Problem Understanding

The problem is asking whether a given m x n matrix of positive integers can be split exactly once, either horizontally or vertically, such that the sums of the two resulting sections are equal, or can be made equal by discounting at most one cell. The catch is that if you discount a cell, the rest of the section must remain connected-meaning you cannot remove a cell in a way that breaks the section into two or more disjoint parts.

The input grid represents the matrix. Each entry grid[i][j] is a positive integer. The output is a boolean indicating whether a valid cut exists under the rules described.

Constraints tell us several important things:

m and n can be as large as 10^5, but the total number of cells m * n is ≤ 10^5. This prevents both dimensions from being simultaneously huge.
Cell values are positive and ≤ 10^5, so integer overflows in most languages are not an issue, but sums can be large.
The minimum size is 2 cells, ensuring that any cut will leave non-empty sections.

Important edge cases include:

Very small grids like 1x2 or 2x1.
Sections that are initially unequal but could be equal if a single edge or corner cell is discounted.
Sections where discounting a middle cell would break connectivity, which is invalid.

The problem requires reasoning about prefix sums, connectivity, and single-cell adjustments, which suggests a combination of array manipulation and smart enumeration.

Approaches

The brute-force approach would consider every possible horizontal and vertical cut. For each cut, compute the sum of both sections and check:

If they are equal, return true.
If they differ, try discounting each cell in the two sections one by one to see if it balances the sums without breaking connectivity.

This approach is correct but too slow. For an m x n grid with k = m * n cells, computing sums for all cuts takes O(k) per cut, and checking all removable cells is O(k) again. With up to k ≈ 10^5, this can lead to O(k^2) operations, which is infeasible.

The key insight for an optimal solution is:

Only one cut is allowed, so we can precompute row sums and column sums. For horizontal cuts, the cumulative row sums let us efficiently compute the sum of the top and bottom sections in O(1) per cut. Similarly for vertical cuts with column sums.
Discounting is restricted to at most one cell, and connectivity constraints simplify the check: the only removable cells without breaking connectivity are the edges of the section along the cut line. This reduces candidate cells drastically to either the topmost/bottommost row or leftmost/rightmost column of the section.
By checking sums and the limited set of removable edge cells, we can efficiently determine if a valid partition exists.

This reduces complexity to O(m + n) for sum computations plus O(1) for discount checks at each cut, which is feasible.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m*n)^2)	O(1)	Check every possible cut and every possible cell removal in both sections
Optimal	O(m*n)	O(m + n)	Use prefix sums for rows/columns and only consider edge cells for possible discount

Algorithm Walkthrough

Compute row sums for horizontal cut checks and column sums for vertical cut checks.
Compute prefix sums of row sums and column sums to quickly calculate section sums for any cut.
For each possible horizontal cut after row i:

Compute top_sum as sum of rows 0..i and bottom_sum as sum of rows i+1..m-1.
If top_sum == bottom_sum, return true.
If not equal, check if removing the topmost row of bottom section or bottommost row of top section can balance the sums.
If yes, return true.

Repeat similar logic for vertical cuts using column sums.
If no valid cut satisfies the conditions, return false.

Why it works: The algorithm checks all possible single cuts. Connectivity constraints mean we only consider edge cells (along the cut) for possible discounting, which preserves section connectivity. Prefix sums guarantee O(1) access to section sums, ensuring efficiency.

Python Solution

from typing import List

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        row_sums = [sum(row) for row in grid]
        col_sums = [sum(grid[i][j] for i in range(m)) for j in range(n)]
        
        # Prefix sums
        pre_row = [0] * m
        pre_row[0] = row_sums[0]
        for i in range(1, m):
            pre_row[i] = pre_row[i-1] + row_sums[i]
        
        pre_col = [0] * n
        pre_col[0] = col_sums[0]
        for j in range(1, n):
            pre_col[j] = pre_col[j-1] + col_sums[j]
        
        total_sum = pre_row[-1]
        
        # Horizontal cuts
        for i in range(m-1):
            top_sum = pre_row[i]
            bottom_sum = total_sum - top_sum
            if top_sum == bottom_sum:
                return True
            diff = abs(top_sum - bottom_sum)
            # Only consider removable cells along cut edge
            if diff in grid[i] or diff in grid[i+1]:
                return True
        
        # Vertical cuts
        for j in range(n-1):
            left_sum = pre_col[j]
            right_sum = total_sum - left_sum
            if left_sum == right_sum:
                return True
            diff = abs(left_sum - right_sum)
            # Only consider removable cells along cut edge
            left_edge = [grid[i][j] for i in range(m)]
            right_edge = [grid[i][j+1] for i in range(m)]
            if diff in left_edge or diff in right_edge:
                return True
        
        return False

Implementation Notes: We first calculate row and column sums and their prefix sums to enable O(1) section sum queries. For discounting, we only need to consider cells along the cut line (edge cells), ensuring connectivity. This makes the solution linear in the number of cells.

Go Solution

func canPartitionGrid(grid [][]int) bool {
    m, n := len(grid), len(grid[0])
    
    rowSums := make([]int, m)
    for i := 0; i < m; i++ {
        sum := 0
        for j := 0; j < n; j++ {
            sum += grid[i][j]
        }
        rowSums[i] = sum
    }
    
    colSums := make([]int, n)
    for j := 0; j < n; j++ {
        sum := 0
        for i := 0; i < m; i++ {
            sum += grid[i][j]
        }
        colSums[j] = sum
    }
    
    preRow := make([]int, m)
    preRow[0] = rowSums[0]
    for i := 1; i < m; i++ {
        preRow[i] = preRow[i-1] + rowSums[i]
    }
    
    preCol := make([]int, n)
    preCol[0] = colSums[0]
    for j := 1; j < n; j++ {
        preCol[j] = preCol[j-1] + colSums[j]
    }
    
    totalSum := preRow[m-1]
    
    // Horizontal cuts
    for i := 0; i < m-1; i++ {
        topSum := preRow[i]
        bottomSum := totalSum - topSum
        if topSum == bottomSum {
            return true
        }
        diff := topSum - bottomSum
        if diff < 0 {
            diff = -diff
        }
        for _, val := range grid[i] {
            if val == diff {
                return true
            }
        }
        for _, val := range grid[i+1] {
            if val == diff {
                return true
            }
        }
    }
    
    // Vertical cuts
    for j := 0; j < n-1; j++ {
        leftSum := preCol[j]
        rightSum := totalSum - leftSum
        if leftSum == rightSum {
            return true
        }
        diff := leftSum - rightSum
        if diff < 0 {
            diff = -diff
        }
        for i := 0; i < m; i++ {
            if grid[i][j] == diff || grid[i][j+1] == diff {
                return true
            }
        }
    }
    
    return false
}

Go-specific Notes: The logic mirrors Python, but we handle slices explicitly. Summations and prefix sums are built using standard loops. Negative differences are corrected manually since Go does not have a built-in abs for integers. Edge