# Equal Sum Grid Partition II
**Difficulty:** HARD
[External](https://leetcode.com/problems/equal-sum-grid-partition-ii)
Canonical: https://scaleengineer.com/dsa/problems/equal-sum-grid-partition-ii
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/equal-sum-grid-partition-ii/image0.jpeg)

* A horizontal cut after the first row gives sums `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:**

![](https://assets.glich.co/dsa/equal-sum-grid-partition-ii/image1.png)

* A vertical cut after the first column gives sums `1 + 3 = 4` and `2 + 4 = 6`.
* By discounting 2 from the right section (`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:**

**![](https://assets.glich.co/dsa/equal-sum-grid-partition-ii/image2.png)**

* A horizontal cut after the first row gives `1 + 2 + 4 = 7` and `2 + 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 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 <= 105`
* `1 <= n == grid[i].length <= 105`
* `2 <= m * n <= 105`
* `1 <= grid[i][j] <= 105`

# Approaches
## Brute-force Check for all Partitions
This approach systematically checks every possible horizontal and vertical cut. For each potential cut, it calculates the sum of elements in the two resulting sections. If the sums are not equal, it naively scans one of the sections to find a cell that can be discounted to make the sums equal, while also checking the connectivity constraint.
**Time:** O(m*n * (m+n)). For each of the `m-1` horizontal cuts, we might iterate over `O(m*n)` cells in the worst case. A similar logic applies to the `n-1` vertical cuts, leading to a very high time complexity. · **Space:** O(m + n) to store the pre-calculated row and column sums.
**Pros:** Simple to conceptualize and implement.; Uses minimal extra space, mainly for storing row and column sums.
**Cons:** Extremely inefficient and will likely result in a 'Time Limit Exceeded' error for larger grids.; The nested loops lead to a high polynomial time complexity.
### Explanation
The brute-force method involves a straightforward, exhaustive search. We begin by pre-calculating row and column sums to avoid re-calculating them for every partition, which is a minor optimization. Then, we loop through each possible horizontal cut line. For each cut, we find the sums of the two resulting partitions. If they aren't equal, we determine the difference, `diff`, and then iterate through every single cell of the larger partition to see if any cell's value matches `diff`. If a match is found, we perform a check to ensure that removing this cell doesn't violate the connectivity rule. The connectivity check is based on the dimensions of the partition: a multi-row, multi-column section always remains connected, but a single-row or single-column section only remains connected if an endpoint is removed. If no valid horizontal cut works, we apply the same logic to all possible vertical cuts. This method is simple but highly inefficient due to the repeated scanning of grid sections.
### Algorithm
- First, pre-calculate the sum of each row and each column to speed up the sum calculation for sections. This takes `O(m*n)` time.
- Iterate through all `m-1` possible horizontal cuts.
- For each horizontal cut, calculate the sum of the top section (`sum1`) and the bottom section (`sum2`).
- Check the three conditions:
  1. If `sum1 == sum2`, a valid partition is found, return `true`.
  2. If `sum1 > sum2`, iterate through every cell in the top section. If a cell's value equals `sum1 - sum2`, check if removing it preserves connectivity. If so, a valid partition is found, return `true`.
  3. If `sum2 > sum1`, perform a similar check on the bottom section.
- If no valid horizontal cut is found, repeat the entire process for all `n-1` possible vertical cuts.
- If no valid partition is found after checking all possible cuts, return `false`.

## Optimized Approach with Pre-computation
This approach dramatically improves performance by pre-computing essential information about the grid. Instead of repeatedly searching for a value to discount, we can query pre-built data structures in constant time. This avoids the nested loops of the brute-force method, reducing the overall time complexity to be linear with respect to the number of cells in the grid.
**Time:** O(m*n). The initial pre-computation pass takes `O(m*n)`. The subsequent loops for checking horizontal and vertical cuts take `O(m)` and `O(n)` time, respectively. The overall complexity is dominated by the pre-computation step. · **Space:** O(m*n). The space is dominated by the HashMaps storing location metadata. In the worst-case scenario where all grid elements are distinct, the maps will store `O(m*n)` entries.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large grids.; The core logic for checking each partition is constant time after the initial setup.
**Cons:** Requires significant extra space to store the location metadata maps, which can be up to `O(m*n)` in the worst case.
### Explanation
This optimized solution hinges on efficient data retrieval. We start with a single `O(m*n)` pass through the grid to gather all necessary information upfront. This includes row/column sums and, crucially, four HashMaps that store the minimum and maximum row/column indices for each unique value in the grid. 

With this pre-computed data, checking each potential cut becomes very fast. For each horizontal cut, we calculate the two partition sums. If they differ, we calculate the required `diff`. To check if we can discount a cell with value `diff` from a partition, we no longer need to scan it. Instead, we use our maps. For instance, to check if `diff` exists in a multi-row, multi-column top partition (rows `0` to `i`), we simply check if `val_to_min_row.get(diff) <= i`. This is an `O(1)` lookup. For single-row or single-column partitions where connectivity is a concern, we perform direct `O(1)` checks on the specific endpoint cells. The same logic is applied to vertical cuts using the column-based maps. This transforms the problem from a high-degree polynomial complexity to a linear one.

```java
import java.util.HashMap;
import java.util.Map;

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

        long[] rowSums = new long[m];
        long[] colSums = new long[n];
        long totalSum = 0;

        Map<Integer, Integer> valToMinRow = new HashMap<>();
        Map<Integer, Integer> valToMaxRow = new HashMap<>();
        Map<Integer, Integer> valToMinCol = new HashMap<>();
        Map<Integer, Integer> valToMaxCol = new HashMap<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = grid[i][j];
                rowSums[i] += val;
                colSums[j] += val;
                totalSum += val;

                valToMinRow.put(val, Math.min(valToMinRow.getOrDefault(val, i), i));
                valToMaxRow.put(val, Math.max(valToMaxRow.getOrDefault(val, i), i));
                valToMinCol.put(val, Math.min(valToMinCol.getOrDefault(val, j), j));
                valToMaxCol.put(val, Math.max(valToMaxCol.getOrDefault(val, j), j));
            }
        }

        // Check horizontal cuts
        long currentSum = 0;
        for (int i = 0; i < m - 1; i++) {
            currentSum += rowSums[i];
            long otherSum = totalSum - currentSum;

            if (currentSum == otherSum) return true;

            long diff = Math.abs(currentSum - otherSum);
            if (diff > Integer.MAX_VALUE) continue;
            int intDiff = (int) diff;

            if (currentSum > otherSum) {
                if (valToMinRow.containsKey(intDiff)) {
                    if (i > 0 && n > 1) { // Multi-row, multi-col top
                        if (valToMinRow.get(intDiff) <= i) return true;
                    } else if (i == 0 && n > 1) { // Single row top
                        if (grid[0][0] == intDiff || grid[0][n - 1] == intDiff) return true;
                    } else if (n == 1 && i > 0) { // Single col top
                        if (grid[0][0] == intDiff || grid[i][0] == intDiff) return true;
                    }
                }
            } else { // otherSum > currentSum
                if (valToMaxRow.containsKey(intDiff)) {
                    if (m - 1 - i > 1 && n > 1) { // Multi-row, multi-col bottom
                        if (valToMaxRow.get(intDiff) >= i + 1) return true;
                    } else if (m - 1 - i == 1 && n > 1) { // Single row bottom
                        if (grid[m - 1][0] == intDiff || grid[m - 1][n - 1] == intDiff) return true;
                    } else if (n == 1 && m - 1 - i > 1) { // Single col bottom
                        if (grid[i + 1][0] == intDiff || grid[m - 1][0] == intDiff) return true;
                    }
                }
            }
        }

        // Check vertical cuts
        currentSum = 0;
        for (int j = 0; j < n - 1; j++) {
            currentSum += colSums[j];
            long otherSum = totalSum - currentSum;

            if (currentSum == otherSum) return true;

            long diff = Math.abs(currentSum - otherSum);
            if (diff > Integer.MAX_VALUE) continue;
            int intDiff = (int) diff;

            if (currentSum > otherSum) {
                if (valToMinCol.containsKey(intDiff)) {
                    if (m > 1 && j > 0) { // Multi-row, multi-col left
                        if (valToMinCol.get(intDiff) <= j) return true;
                    } else if (m > 1 && j == 0) { // Single col left
                        if (grid[0][0] == intDiff || grid[m - 1][0] == intDiff) return true;
                    } else if (m == 1 && j > 0) { // Single row left
                        if (grid[0][0] == intDiff || grid[0][j] == intDiff) return true;
                    }
                }
            } else { // otherSum > currentSum
                if (valToMaxCol.containsKey(intDiff)) {
                    if (m > 1 && n - 1 - j > 1) { // Multi-row, multi-col right
                        if (valToMaxCol.get(intDiff) >= j + 1) return true;
                    } else if (m > 1 && n - 1 - j == 1) { // Single col right
                        if (grid[0][n - 1] == intDiff || grid[m - 1][n - 1] == intDiff) return true;
                    } else if (m == 1 && n - 1 - j > 1) { // Single row right
                        if (grid[0][j + 1] == intDiff || grid[0][n - 1] == intDiff) return true;
                    }
                }
            }
        }

        return false;
    }
}
```
### Algorithm
- Perform a single pass over the grid to pre-compute the following data in `O(m*n)` time:
  - `row_sums`: an array with the sum of each row.
  - `col_sums`: an array with the sum of each column.
  - `total_sum`: the sum of all elements in the grid.
  - Four HashMaps to store location metadata for each distinct value `v`:
    - `val_to_min_row`: maps `v` to its minimum row index.
    - `val_to_max_row`: maps `v` to its maximum row index.
    - `val_to_min_col`: maps `v` to its minimum column index.
    - `val_to_max_col`: maps `v` to its maximum column index.
- **Horizontal Cuts:** Iterate from `i = 0` to `m-2`. Calculate `top_sum` and `bottom_sum`.
  - If sums are equal, return `true`.
  - Otherwise, calculate `diff` and use the pre-computed maps and direct corner checks to see if a valid discount is possible in `O(1)` time.
- **Vertical Cuts:** Perform a similar `O(1)` check for each vertical cut from `j = 0` to `n-2` using the column-based metadata maps.
- If any check passes, return `true`. If all checks fail, return `false`.