By Expert Funda Thursday, March 26, 2026

LeetCode Weekly Contest 449 · Problem 3

3548. Equal Sum Grid Partition II

⬤ Hard Prefix Sum Hash Table Matrix Enumeration O(m·n) time
Problem Statement

What are we solving?

You have a 2D grid of positive integers. Make exactly one straight cut — either a full horizontal line (between two rows) or a full vertical line (between two columns) — splitting the grid into exactly two non-empty halves.

Goal: Can you make the two halves have equal sums? You are allowed to optionally remove one cell from one of the halves first — but only if the remaining cells stay connected (4-directionally).

Key Connectivity Rule: A cell can be discarded only if it sits on the boundary of its section — specifically adjacent to the cut or on an outer edge — so that removing it doesn't create a disconnected hole.

Return true if a valid cut exists, false otherwise.

💡 Core Intuition

For any horizontal cut after row i, compute topSum and botSum. Their difference is diff = topSum − botSum. To balance the two halves you need to remove a cell whose value equals |diff| from the heavier side.

Connectivity simplification: For a rectangular section, the only cells that can be safely removed without disconnecting it are border cells. For our 4-direction sweep trick, this reduces to: any cell in the rows/columns already accumulated in our scan is a valid candidate (valid for 2-column grids; generalises with corner checks for wider grids).
4-Direction Trick: Instead of writing 4 separate loops, run one canPartition() function on 4 variants of the grid — original, reversed, transposed, and reversed+transposed — to cover all horizontal and vertical cut directions including both boundary sides.
🔢 Algorithm Steps
  • 1
    Compute total sum of entire grid once. O(m×n).
  • 2
    Run canPartition() on 4 orientations:
    ① Original → H-cuts top→bottom
    ② Reversed rows → H-cuts bottom→top
    ③ Transposed → V-cuts left→right
    ④ Reversed+Transposed → V-cuts right→left
  • 3
    Inside canPartition: Sweep row by row, accumulating topSum. Compute diff = topSum − botSum at each position.
  • 4
    Four early-return checks:
    diff == 0 → already balanced
    diff == grid[0][0] → remove top-left corner
    diff == grid[0][last] → remove top-right corner
    diff == grid[i][0] → remove cut-edge first cell
  • 5
    HashSet seen accumulates all cell values from rows scanned so far. If diff is in seen (and constraints hold), return true. ⚠ Must guard against integer overflow here!
☕ Java Solution
Java 
import java.util.*;

class Solution {

  public boolean canPartitionGrid(int[][] grid) {
    final long sum = Arrays.stream(grid)
        .flatMapToInt(Arrays::stream)
        .asLongStream().sum();

    return canPartition(grid, sum)
        || canPartition(reversed(grid), sum)
        || canPartition(transposed(grid), sum)
        || canPartition(reversed(transposed(grid)), sum);
  }

  private boolean canPartition(int[][] grid, long sum) {
    long topSum = 0;
    Set<Integer> seen = new HashSet<>();

    for (int i = 0; i < grid.length; ++i) {
      topSum += Arrays.stream(grid[i]).asLongStream().sum();
      final long botSum = sum - topSum;
      final long diff   = topSum - botSum;

      Arrays.stream(grid[i]).forEach(seen::add);

      // Case 1: already balanced
      if (diff == 0) return true;

      // Cases 2-4: remove a corner / cut-edge cell
      if (diff == grid[0][0])                      return true;
      if (diff == grid[0][grid[0].length - 1])    return true;
      if (diff == grid[i][0])                      return true;

      // Case 5: any seen cell matches diff
      // ✅ Guard: cell values ∈ [1,100000] — prevents int overflow cast
      if (grid[0].length > 1 && i > 0
          && diff >= 1 && diff <= 100_000
          && seen.contains((int) diff))
        return true;
    }
    return false;
  }

  // Transpose: rows become columns
  private int[][] transposed(int[][] grid) {
    int[][] res = new int[grid[0].length][grid.length];
    for (int i = 0; i < grid.length; i++)
      for (int j = 0; j < grid[0].length; j++)
        res[j][i] = grid[i][j];
    return res;
  }

  // Reverse row order
  private int[][] reversed(int[][] grid) {
    return Arrays.stream(grid)
        .collect(java.util.stream.Collectors.collectingAndThen(
            java.util.stream.Collectors.toList(),
            list -> {
              Collections.reverse(list);
              return list.toArray(new int[0][]);
            }));
  }
}
🐛 The Integer Overflow Bug

⚠ Root Cause: (int) diff silently overflows

The original walkccc reference solution writes:

seen.contains((int)(topSum - botSum))

Here diff = topSum − botSum is a long. On large grids (thousands of rows × 100,000 values), diff can exceed Integer.MAX_VALUE (~2.1 billion). Casting such a value to int silently wraps around in Java — producing a garbage integer that may accidentally equal a cell value in seen, triggering a false positive.

Concrete example: A grid with 50,000 rows of [100000, 100000] has total = 10¹⁰. Near the last row, diff ≈ 10¹⁰ > 2³¹. Casting: (int)(10_000_000_000L) = 1_410_065_408 — which could accidentally match a value in seen and incorrectly return true.

The test case you provided has exactly this structure: a very large 2-column grid with thousands of rows of [100000, 100000], causing diff to grow beyond Integer.MAX_VALUE at later cut positions.

✅ The Fix

✓ Guard with a value-range check

Since all grid cell values are bounded to [1, 100_000], diff can only ever legitimately match a cell value when it falls in that range. Add this guard before casting:

Before (Buggy) 
// ❌ WRONG — (int) diff overflows when diff > Integer.MAX_VALUE
if (grid[0].length > 1 && i > 0 && seen.contains((int) (topSum - botSum)))
  return true;
After (Fixed) 
// ✅ CORRECT — range guard prevents overflow cast
final long diff = topSum - botSum;
if (grid[0].length > 1 && i > 0
    && diff >= 1 && diff <= 100_000   // ← the fix
    && seen.contains((int) diff))
  return true;
Why this works: The range check diff >= 1 && diff <= 100_000 short-circuits before the cast whenever diff is out of the valid cell-value range. The (int) cast is now only reached when diff is guaranteed to fit safely.
⚖ Other Approaches
✓ Optimal

Prefix Sum + HashSet (4 sweeps)

Sweep in all 4 directions via transformation. Track seen values, check diff.

+ O(mn) time, linear space
+ Clean, concise code
− Subtle edge cases (overflow, corners)
✗ Brute Force

Check all cuts × all cells

For each cut, try removing every border cell with BFS connectivity check.

+ Easy to understand
− O(m²n + mn²) — TLE on large grids
− Needs full BFS/DFS per attempt
~ Alternative

Prefix Sum + Value Map

Precompute row/col sums. For each cut, look up diff in a value→position map and verify boundary.

+ Explicit position tracking
− More complex; duplicate values need care
⊘ Overkill

Segment Tree on Rows/Cols

Build a segment tree for fast range sum queries. Useful for dynamic updates, not this problem.

+ Flexible for dynamic grids
− O(mn log mn) — worse than optimal
− Massive over-engineering
📊 Complexity Comparison
Approach Time Space Recommended
Prefix Sum + HashSet (fixed) O(mn) O(mn) ✓ Yes
Prefix Sum + HashSet (original) O(mn) O(mn) ✗ Overflow bug
Value Map approach O(mn) O(mn) ~ Viable
Brute Force O(m²n²) O(mn) ✗ TLE
Continue Reading →