LeetCode 3546 - Equal Sum Grid Partition I

This problem asks us to determine whether a rectangular grid of positive integers can be split into two parts with exactly the same sum using a single straight cut. The cut can be made in only one of two ways: - A horizontal cut between two adjacent rows.

leetcodemediumarraymatrixenumerationprefix-sum

LeetCode Problem 3546

Difficulty: 🟡 Medium
Topics: Array, Matrix, Enumeration, Prefix Sum

Solution

LeetCode 3546 - Equal Sum Grid Partition I

Problem Understanding

This problem asks us to determine whether a rectangular grid of positive integers can be split into two parts with exactly the same sum using a single straight cut.

The cut can be made in only one of two ways:

  • A horizontal cut between two adjacent rows.
  • A vertical cut between two adjacent columns.

After making the cut, both resulting sections must contain at least one cell. Therefore, we cannot cut above the first row, below the last row, left of the first column, or right of the last column.

The input is an m x n matrix grid, where every cell contains a positive integer. We must return true if there exists at least one valid horizontal or vertical cut that produces two non-empty sections whose sums are equal. Otherwise, we return false.

The constraints are particularly important:

  • 1 <= m, n <= 10^5
  • 2 <= m * n <= 10^5

Although either dimension may be very large, the total number of cells is at most 10^5. This means algorithms proportional to the total number of cells are feasible, but algorithms that repeatedly recompute sums for large portions of the grid are too expensive.

A naive implementation might repeatedly calculate the sum of both sides for every possible cut. Since there can be up to m - 1 + n - 1 possible cuts, recomputing sums from scratch would lead to excessive work.

Important edge cases include single-row grids, single-column grids, grids whose total sum is odd, and cases where the valid partition occurs only at the final possible cut position. The problem guarantees that all values are positive integers, which simplifies sum calculations and avoids complications involving negative numbers.

Approaches

Brute Force

A straightforward approach is to examine every possible horizontal and vertical cut.

For each horizontal cut, we compute the sum of all rows above the cut and the sum of all rows below the cut. Similarly, for each vertical cut, we compute the sum of all columns on the left and right sides.

This approach is correct because it explicitly checks every valid partition. If any partition has equal sums, we return true.

The problem is that recomputing sums for every cut is expensive. A horizontal cut may require scanning most of the grid, and the same is true for a vertical cut. Since there can be up to O(m + n) cut positions, the total running time becomes too large.

Optimal Approach: Prefix Sum Accumulation

The key observation is that every cut divides the grid into two complementary parts.

Suppose the total grid sum is total.

If a horizontal cut produces an upper section with sum upper, then the lower section automatically has sum total - upper.

The partition is valid exactly when:

upper = total - upper

which means:

upper = total / 2

The same logic applies to vertical cuts.

Therefore, instead of recomputing sums repeatedly, we can:

  1. Compute the total grid sum once.
  2. Scan rows from top to bottom while maintaining a running prefix sum.
  3. Check whether the prefix sum equals half of the total.
  4. Repeat the same process for columns.

Because every cell contributes to exactly one row sum and one column sum calculation, the entire solution runs in linear time relative to the number of cells.

Approach Time Complexity Space Complexity Notes
Brute Force O((m + n) × m × n) O(1) Recomputes partition sums for every cut
Optimal O(m × n) O(1) Single pass for total sum, row cuts, and column cuts

Algorithm Walkthrough

  1. Compute the total sum of all elements in the grid.
  2. If the total sum is odd, immediately return false. Two equal integer sums cannot add up to an odd total.
  3. Let target = total // 2. Any valid partition must have one side summing exactly to this value.
  4. Check all horizontal cuts. Maintain a running sum representing the rows above the current cut. After adding each row, except the last one, compare the running sum with target. If they are equal, return true.
  5. If no horizontal cut works, check all vertical cuts. Maintain a running sum representing the columns to the left of the current cut. For each column, add all values in that column to the running sum. After processing each column except the last one, compare the running sum with target. If they are equal, return true.
  6. If neither horizontal nor vertical cuts produce equal sums, return false.

Why it works

The algorithm relies on the fact that every valid partition divides the grid into two complementary regions whose sums add up to the total sum. Therefore, a partition is valid if and only if one side equals exactly half of the total. By examining every possible horizontal and vertical cut while maintaining prefix sums, we test every legal partition exactly once. Since every valid cut is checked, the algorithm cannot miss a solution.

Problem Understanding

The problem asks us to determine whether a given m x n matrix of positive integers can be split into two non-empty sections with equal sums by making a single horizontal or vertical cut. In other words, we can either cut between two rows (horizontal cut) or two columns (vertical cut) but not both. Each resulting section must contain at least one row or column.

The input grid represents a two-dimensional array of integers. The expected output is a boolean: true if a valid partition exists, and false otherwise. The constraints tell us that the total number of elements, m * n, will not exceed 10^5, which means a brute-force approach iterating through all subgrids would be too slow. Each element is positive, so we do not need to handle negative sums, but large sums can occur, requiring careful accumulation.

Important edge cases include a single row or single column (partition may still be possible), grids where all values are the same, and grids where the total sum is odd (partition is impossible because two equal sums require an even total).

Approaches

Brute Force Approach

The brute-force approach would iterate over every possible horizontal and vertical cut, calculate the sum of elements in the two resulting sections, and check if they are equal. For horizontal cuts, we sum the top i rows and compare it to the sum of the remaining rows. For vertical cuts, we sum the first j columns and compare to the remaining columns. This method is correct but inefficient because each sum calculation requires traversing a large portion of the grid repeatedly, resulting in a time complexity of O(m * n * (m + n)), which is far too slow for m * n up to 10^5.

Optimal Approach

The key insight for an optimal solution is prefix sums. We can precompute the sum of each row and each column. Then, we iterate once through possible horizontal and vertical cuts, checking whether the sum of rows or columns up to that point equals half of the total sum. This reduces redundant computation, giving a linear time solution.

Comparison Table

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * (m + n)) O(1) Compute sums for each potential cut without optimization
Optimal O(m * n) O(m + n) Use prefix sums to check partitions efficiently

Algorithm Walkthrough

  1. Compute the sum of each row and store it in a row_sums array. Similarly, compute the sum of each column and store it in a col_sums array. This allows efficient calculation of total sums for horizontal and vertical sections.
  2. Calculate the total sum of the grid by summing all row sums (or column sums). If the total sum is odd, immediately return false because equal partition is impossible.
  3. Iterate through potential horizontal cuts. Keep a running sum of rows from the top. At each row, check if the running sum equals half of the total sum. If yes, return true.
  4. Iterate through potential vertical cuts. Keep a running sum of columns from the left. At each column, check if the running sum equals half of the total sum. If yes, return true.
  5. If no horizontal or vertical cut produces equal sections, return false.

Why it works: The algorithm relies on the property that any valid cut must divide the total sum exactly in half. By precomputing sums along rows and columns, we ensure we can check all cuts efficiently without recalculating section sums multiple times.

Python Solution

from typing import List

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

        total_sum = sum(sum(row) for row in grid)

        if total_sum % 2 == 1:
            return False

        target = total_sum // 2

        prefix_sum = 0
        for row in range(m - 1):
            prefix_sum += sum(grid[row])
            if prefix_sum == target:
                return True

        prefix_sum = 0
        for col in range(n - 1):
            for row in range(m):
                prefix_sum += grid[row][col]

            if prefix_sum == target:
                return True

        return False

The implementation begins by computing the dimensions and total sum of the grid. If the total sum is odd, the function immediately returns False because no equal partition can exist.

Next, the code scans all possible horizontal cuts. The variable prefix_sum stores the cumulative sum of rows above the current cut. Since the cut must leave both sections non-empty, the loop stops at m - 1.

If no horizontal cut succeeds, the algorithm performs the same idea for columns. The running sum now represents all columns to the left of the cut. Again, the final column is excluded because a cut after the last column would leave an empty section.

If either scan reaches the target half-sum, a valid partition exists and the function returns True. Otherwise, all cuts have been tested and the answer is False. m, n = len(grid), len(grid[0])

    # Compute row sums and column 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)]
    
    total_sum = sum(row_sums)
    if total_sum % 2 != 0:
        return False
    
    half_sum = total_sum // 2
    
    # Check horizontal cuts
    running_sum = 0
    for r_sum in row_sums[:-1]:  # cannot cut after last row
        running_sum += r_sum
        if running_sum == half_sum:
            return True
    
    # Check vertical cuts
    running_sum = 0
    for c_sum in col_sums[:-1]:  # cannot cut after last column
        running_sum += c_sum
        if running_sum == half_sum:
            return True
    
    return False


The Python code first computes row and column sums for efficient lookup. It checks whether the total sum is even, then iterates through possible cuts using running sums. We stop early if a valid partition is found.

## Go Solution

```go
func canPartitionGrid(grid [][]int) bool {
	m := len(grid)
	n := len(grid[0])

	var totalSum int64

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			totalSum += int64(grid[i][j])
		}
	}

	if totalSum%2 == 1 {
		return false
	}

	target := totalSum / 2

	var prefixSum int64

	for row := 0; row < m-1; row++ {
		for col := 0; col < n; col++ {
			prefixSum += int64(grid[row][col])
		}

		if prefixSum == target {
			return true
		}
	}

	prefixSum = 0

	for col := 0; col < n-1; col++ {
		for row := 0; row < m; row++ {
			prefixSum += int64(grid[row][col])
		}

		if prefixSum == target {
			return true
		}
	}

	return false
}

The Go implementation follows the same logic as the Python version. The main difference is the use of int64 for all sum calculations. The maximum possible total sum can reach 10^5 × 10^5 = 10^10, which exceeds the range of a 32-bit integer. Using int64 prevents overflow and ensures correctness.

Worked Examples

Example 1

grid = [
    [1, 4],
    [2, 3]
]

Total sum:

Cell Values Sum
1 + 4 + 2 + 3 10

Target:

Total Target
10 5

Horizontal scan:

Row Processed Prefix Sum Equals Target?
[1,4] 5 Yes

A valid horizontal cut exists.

Result:

true

Example 2

grid = [
    [1, 3],
    [2, 4]
]

Total sum:

Calculation Value
1 + 3 + 2 + 4 10

Target:

Total Target
10 5

Horizontal scan:

Row Processed Prefix Sum
[1,3] 4

No match.

Vertical scan:

Column Processed Prefix Sum
[1,2] 3

No match.

Result:

false

Detailed Trace

Step Action Value
1 Total sum 10
2 Target 5
3 First row prefix 4
4 First column prefix 3
5 No prefix equals 5 Return false
m, n := len(grid), len(grid[0]) 
rowSums := make([]int, m)
colSums := make([]int, n)

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

if totalSum%2 != 0 {
    return false
}

halfSum := totalSum / 2

runningSum := 0
for i := 0; i < m-1; i++ {
    runningSum += rowSums[i]
    if runningSum == halfSum {
        return true
    }
}

runningSum = 0
for j := 0; j < n-1; j++ {
    runningSum += colSums[j]
    if runningSum == halfSum {
        return true
    }
}

return false

}


The Go implementation mirrors the Python version, using slices to store row and column sums. Go requires explicit initialization of slices and integer division is safe because all sums are positive.

## Worked Examples

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

Total sum = 1+4+2+3 = 10, half = 5

**Horizontal sums:**

row_sums = [5, 5]

running_sum = 5 after first row → equals half → return true

**Vertical sums:**

col_sums = [3, 7]

running_sum after first column = 3 → not half → continue → cannot cut after last column

Output: true

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

Total sum = 10, half = 5

**Horizontal sums:**

row_sums = [4, 6]

running_sum after first row = 4 → not half

**Vertical sums:**

col_sums = [3, 7]

running_sum after first column = 3 → not half

No valid cut → return false

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(m × n) | Every cell is processed a constant number of times |
| Space | O(1) | Only a few running sum variables are used |

The algorithm performs one full traversal to compute the total sum. The horizontal scan processes each cell once through row summation, and the vertical scan processes each cell once through column summation. Since constant factors are ignored in asymptotic analysis, the overall complexity remains `O(m × n)`. No auxiliary arrays or prefix tables are required, so the extra space usage is constant.

## Test Cases

```python
from typing import List

s = Solution()

assert s.canPartitionGrid([[1, 4], [2, 3]]) is True      # example 1
assert s.canPartitionGrid([[1, 3], [2, 4]]) is False     # example 2

assert s.canPartitionGrid([[1, 1]]) is True              # single row
assert s.canPartitionGrid([[1], [1]]) is True            # single column

assert s.canPartitionGrid([[5, 5]]) is True              # vertical cut

assert s.canPartitionGrid([[2], [2]]) is True            # horizontal cut

assert s.canPartitionGrid([[1, 2], [3, 5]]) is False     # odd total sum

assert s.canPartitionGrid([[1, 2, 3]]) is True           # single row, vertical partition

assert s.canPartitionGrid([[1], [2], [3]]) is True       # single column, horizontal partition

assert s.canPartitionGrid([[10]]) is False               # no valid cut possible

assert s.canPartitionGrid([[1, 2], [1, 2], [2, 4]]) is True  # later horizontal cut

assert s.canPartitionGrid([[1, 1, 2], [1, 1, 2]]) is True    # multiple valid cuts
| Time | O(m * n) | Calculating row sums, column sums, and total sum requires scanning all elements once. Checking cuts is O(m + n). |
| Space | O(m + n) | Extra arrays for row sums and column sums. |

The algorithm is linear with respect to the number of elements, which is optimal given we must inspect every element at least once.

## Test Cases

Provided examples

assert Solution().canPartitionGrid([[1,4],[2,3]]) == True # horizontal cut possible assert Solution().canPartitionGrid([[1,3],[2,4]]) == False # no cut possible

Single row

assert Solution().canPartitionGrid([[1,2,3,6]]) == True # vertical cut after last 3 assert Solution().canPartitionGrid([[1,2,3]]) == False # odd sum

Single column

assert Solution().canPartitionGrid([[1],[1]]) == True # horizontal cut assert Solution().canPartitionGrid([[1],[2]]) == False # sum cannot be divided

Uniform grid

assert Solution().canPartitionGrid([[2,2],[2,2]]) == True # any cut works

Larger grid

assert Solution().canPartitionGrid([[1]*1000 for _ in range(100)]) == True # horizontal or vertical cut works


| Test | Why |
| --- | --- |
| `[[1,4],[2,3]]` | Official positive example |
| `[[1,3],[2,4]]` | Official negative example |
| `[[1,1]]` | Smallest valid single-row grid |
| `[[1],[1]]` | Smallest valid single-column grid |
| `[[5,5]]` | Vertical cut success |
| `[[2],[2]]` | Horizontal cut success |
| `[[1,2],[3,5]]` | Odd total sum |
| `[[1,2,3]]` | One-row grid |
| `[[1],[2],[3]]` | One-column grid |
| `[[10]]` | No legal cut exists |
| `[[1,2],[1,2],[2,4]]` | Valid cut near end |
| `[[1,1,2],[1,1,2]]` | Multiple possible partitions |

## Edge Cases

### Single Row Grid

When `m = 1`, horizontal cuts are impossible because any cut would leave an empty section. A buggy implementation might still attempt to evaluate such cuts. The solution naturally handles this because the horizontal loop runs from `0` to `m - 2`, resulting in zero iterations. Only vertical cuts are considered.

### Single Column Grid

When `n = 1`, vertical cuts are impossible. The algorithm correctly skips the vertical scan because the loop runs only until `n - 2`. Horizontal cuts remain available and are checked normally.

### Odd Total Sum

If the total grid sum is odd, an equal partition is mathematically impossible. Failing to detect this early could waste time checking cuts that can never work. The implementation immediately returns `False` when `total_sum % 2 == 1`.

### Valid Cut at the Last Possible Position

A common off-by-one mistake is forgetting to consider cuts immediately before the final row or final column. The algorithm checks all cut positions from the first valid location through the last valid location by iterating up to `m - 1` rows and `n - 1` columns, ensuring every legal partition is examined.

### Large Grid Values

Each cell may contain values up to `10^5`, and there can be up to `10^5` cells. The total sum can therefore reach `10^10`. The Go implementation uses `int64` for accumulation to avoid integer overflow, ensuring correctness for the largest inputs.
| [[1,4],[2,3]] | Horizontal cut success |
| [[1,3],[2,4]] | No cut possible |
| [[1,2,3,6]] | Single row, vertical cut |
| [[1],[2]] | Single column, impossible partition |
| [[2,2],[2,2]] | Uniform grid, any cut valid |
| 100x1000 grid of 1s | Stress test, large input |

## Edge Cases

1. **Single row or single column**: Grids with only one row or one column can still be partitioned vertically or horizontally. The code handles this by iterating only to `n-1` or `m-1`, avoiding cuts that would produce empty sections.
2. **Odd total sum**: If the sum of all elements is odd, no equal