Watch 10 video solutions for Equal Sum Grid Partition I, a medium level problem involving Array, Matrix, Enumeration. This walkthrough by codestorywithMIK has 6,098 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.
Example 1:
Input: grid = [[1,4],[2,3]]
Output: true
Explanation:
A horizontal cut between row 0 and row 1 results in two non-empty sections, each with a sum of 5. Thus, the answer is true.
Example 2:
Input: grid = [[1,3],[2,4]]
Output: false
Explanation:
No horizontal or vertical cut results in two non-empty sections with equal sums. Thus, 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 cut can divide the grid into two parts with equal total sum. The cut must split the grid along row or column boundaries, and both resulting regions must have the same sum.
Approach 1: Brute Force Enumeration (O(m*n*(m+n)) time, O(1) space)
Start by computing the total sum of the grid. Then try every possible horizontal cut and vertical cut. For each candidate cut, iterate through the relevant portion of the grid and compute the sum of both partitions directly. A horizontal cut requires summing rows above and below the cut; a vertical cut requires summing columns on both sides. This method is straightforward but inefficient because each cut recomputes large portions of the grid, leading to repeated work across iterations.
Approach 2: Enumeration + Prefix Sum (O(m*n) time, O(m+n) space)
Compute the total grid sum first. Then build running prefix sums for rows and columns while scanning the grid. For horizontal partitions, maintain a cumulative sum of rows from top to bottom. After processing each row, check whether the accumulated sum equals half of the total grid sum. For vertical partitions, maintain cumulative column sums while iterating across columns and perform the same comparison. This avoids recomputing sums for every candidate cut because each prefix value represents the sum of an entire region. The key insight is that any valid partition must split the total sum exactly in half, so you only check whether a prefix region equals totalSum / 2.
The solution relies on efficient grid traversal and incremental accumulation, which fits naturally with Prefix Sum techniques. The cut positions are tested through simple Enumeration while scanning the Matrix.
Recommended for interviews: Enumeration combined with prefix sums is the expected approach. The brute force version demonstrates the core idea of testing every possible cut, but the optimized prefix accumulation shows that you understand how to eliminate redundant work and reduce the complexity to O(m*n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(m*n*(m+n)) | O(1) | Useful for understanding the partition idea or when constraints are extremely small |
| Enumeration + Prefix Sum | O(m*n) | O(m+n) | Best general solution for large grids; avoids recomputing sums for every possible cut |