Watch 10 video solutions for Equal Sum Grid Partition II, a hard level problem involving Array, Hash Table, Matrix. This walkthrough by codestorywithMIK has 9,929 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n matrix grid of positive integers. Your task is to determine if it is possible to make either one horizontal or one vertical cut on the grid such that:
Return true if such a partition exists; otherwise, return false.
Note: A section is connected if every cell in it can be reached from any other cell by moving up, down, left, or right through other cells in the section.
Example 1:
Input: grid = [[1,4],[2,3]]
Output: true
Explanation:
1 + 4 = 5 and 2 + 3 = 5, which are equal. Thus, the answer is true.Example 2:
Input: grid = [[1,2],[3,4]]
Output: true
Explanation:
1 + 3 = 4 and 2 + 4 = 6.6 - 2 = 4), both sections have equal sums and remain connected. Thus, the answer is true.Example 3:
Input: grid = [[1,2,4],[2,3,5]]
Output: false
Explanation:
1 + 2 + 4 = 7 and 2 + 3 + 5 = 10.10 - 3 = 7), both sections have equal sums, but they do not remain connected as it splits the bottom section into two parts ([2] and [5]). Thus, the answer is false.Example 4:
Input: grid = [[4,1,8],[3,2,6]]
Output: false
Explanation:
No valid cut exists, so the answer is false.
Constraints:
1 <= m == grid.length <= 1051 <= n == grid[i].length <= 1052 <= m * n <= 1051 <= grid[i][j] <= 105Problem Overview: You are given a 2D grid of integers and need to determine whether a single horizontal or vertical partition can split the grid into two regions whose sums are equal. The challenge comes from efficiently computing region sums while exploring all valid partition positions.
Approach 1: Brute Force Grid Partition (O(m * n * (m + n)) time, O(1) space)
The most direct strategy is to try every possible horizontal and vertical cut. For each candidate partition, iterate through the cells on both sides and compute their sums independently. Compare the two totals to check whether they match. This approach requires repeatedly scanning large portions of the matrix, which makes it slow for large grids. It’s useful mainly for validating correctness or building intuition before optimizing.
Approach 2: Prefix Sum Matrix (O(m * n) time, O(m * n) space)
Build a 2D prefix sum matrix so you can query the sum of any sub-rectangle in constant time. After preprocessing, iterate over every possible horizontal and vertical partition. Use the prefix table to compute the sum of the two resulting regions instantly. This removes repeated summations across the grid and reduces the complexity significantly. The main tradeoff is the extra memory required to store the prefix matrix.
Approach 3: Row/Column Accumulation with Hash Checks (O(m * n) time, O(m + n) space)
A more memory‑efficient method uses running row or column totals instead of a full 2D prefix structure. First compute the total grid sum. Then iterate through rows accumulating the top portion sum; the remaining part automatically forms the bottom sum. Repeat the same idea for vertical partitions using column totals. A hash table or simple arithmetic comparison helps verify whether the two regions match the required half of the total. This approach avoids heavy memory usage while keeping constant-time checks per partition.
Recommended for interviews: Interviewers typically expect the prefix sum or running accumulation solution with O(m * n) time. Starting with the brute force explanation shows you understand the partition logic, but optimizing with prefix sums or incremental totals demonstrates strong algorithmic thinking and familiarity with matrix optimization patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Partition | O(m * n * (m + n)) | O(1) | Conceptual baseline or very small grids |
| 2D Prefix Sum | O(m * n) | O(m * n) | General case where fast subgrid sum queries are needed |
| Row/Column Accumulation | O(m * n) | O(m + n) | Optimal interview solution with lower memory usage |