Equal Sum Grid Partition II - Video Solutions
Equal Sum Grid Partition II | Detailed | Simplified Approach | Leetcode 3548 | codestorywithMIK
Equal Sum Grid Partition II - Video Solution
Watch 10 video solutions for Equal Sum Grid Partition II, a hard level problem involving Array, Hash Table, Matrix. This walkthrough by codestorywithMIK has 10,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- Each of the two resulting sections formed by the cut is non-empty.
- The sum of elements in both sections is equal, or can be made equal by discounting at most one single cell in total (from either section).
- If a cell is discounted, the rest of the section must remain connected.
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:
- A horizontal cut after the first row gives sums
1 + 4 = 5and2 + 3 = 5, which are equal. Thus, the answer istrue.
Example 2:
Input: grid = [[1,2],[3,4]]
Output: true
Explanation:
- A vertical cut after the first column gives sums
1 + 3 = 4and2 + 4 = 6. - By discounting 2 from the right section (
6 - 2 = 4), both sections have equal sums and remain connected. Thus, the answer istrue.
Example 3:
Input: grid = [[1,2,4],[2,3,5]]
Output: false
Explanation:
- A horizontal cut after the first row gives
1 + 2 + 4 = 7and2 + 3 + 5 = 10. - By discounting 3 from the bottom section (
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 isfalse.
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] <= 105
Approach Overview
Problem 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.
Complexity Analysis
| 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 |