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.
We can first enumerate horizontal partition lines, compute the element sum of each resulting part, and use hash maps to record the occurrence count of elements in each part.
For each partition line, we need to determine whether the sums of the two parts are equal, or whether removing one cell can make them equal. If the sums are equal, we directly return true. If the sums are not equal, we compute their difference diff. If diff exists in the hash map of the larger part and satisfies the connectivity condition after removing that cell, we also return true.
The connectivity condition can be checked using the following criteria:
1 row and more than 1 column.1 row, and the removed cell is on the boundary of that part (i.e., the first column or the last column).1 row, and the removed cell is on the boundary of that part (i.e., the first row or the last row).Satisfying any one of the above conditions guarantees that the part remains connected after removing the cell.
We also need to enumerate vertical partition lines, which is similar to the horizontal case. To simplify the enumeration of vertical partition lines, we can first transpose the matrix and then apply the same logic.
The time complexity is O(m times n) and the space complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively.
Python
Java
C++
Go
TypeScript
| 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 |
Equal Sum Grid Partition II | Detailed | Simplified Approach | Leetcode 3548 | codestorywithMIK • codestorywithMIK • 9,929 views views
Watch 9 more video solutions →Practice Equal Sum Grid Partition II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor