CodeWithIshwar

Posted on Mar 25

# I Overcomplicated This Grid Problem… Until Prefix Sum Saved Me

#leetcode #java #programming #dsa

Sometimes the problem isn’t hard — we just make it harder.

While solving Equal Sum Grid Partition (LeetCode 3546), I caught myself doing exactly that.

🧩 Problem Overview

You’re given an m x n grid of positive integers.

You need to make one cut (horizontal or vertical) such that:

Both parts are non-empty
Both parts have equal sum

🤯 My First Approach (Wrong Direction)

My initial thought was:

“Let’s try all possible cuts.”

Try every horizontal cut
Try every vertical cut
Compare sums

This works… but:

❌ Feels brute-force
❌ Gets messy quickly
❌ Not scalable thinking

💡 The Insight That Changed Everything

I paused and asked:

👉 What does “equal sum” actually mean?

If both parts must be equal:

Each part must be totalSum / 2

Now the problem becomes much simpler:

👉 Can we find a prefix sum (row-wise or column-wise) equal to half of the total?

⚙️ Optimized Approach

Step 1: Compute total sum

If total is odd → return false

Step 2: Check horizontal cuts

Accumulate row-wise prefix
Stop at m - 1 (to keep bottom non-empty)

Step 3: Check vertical cuts

Precompute column sums
Accumulate column-wise prefix

💻 Java Implementation

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        long total = 0;

        for (int[] row : grid) {
            for (int val : row) {
                total += val;
            }
        }

        if (total % 2 != 0) return false;

        long half = total / 2;

        long prefix = 0;

        // Horizontal cut
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n; j++) {
                prefix += grid[i][j];
            }
            if (prefix == half) return true;
        }

        // Vertical cut
        long[] colSum = new long[n];

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colSum[j] += grid[i][j];
            }
        }

        prefix = 0;
        for (int j = 0; j < n - 1; j++) {
            prefix += colSum[j];
            if (prefix == half) return true;
        }

        return false;
    }
}

⏱ Complexity

Time: O(m × n)
Space: O(n)

🔥 Key Takeaway

The problem wasn’t about trying all possibilities —
it was about recognizing a pattern.

DEV Community