# Equal Sum Grid Partition I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/equal-sum-grid-partition-i)
Canonical: https://scaleengineer.com/dsa/problems/equal-sum-grid-partition-i
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, 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 the elements in both sections is **equal**.

Return `true` if such a partition exists; otherwise return `false`.

**Example 1:**

**Input:** grid = \[\[1,4\],\[2,3\]\]

**Output:** true

**Explanation:**

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

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 <= 105`
* `1 <= n == grid[i].length <= 105`
* `2 <= m * n <= 105`
* `1 <= grid[i][j] <= 105`

# Approaches
## Brute Force Iteration
This approach involves iterating through every possible horizontal and vertical cut. For each potential cut, it calculates the sum of the elements in the two resulting partitions from scratch and checks if they are equal.
**Time:** O(m*n * (m+n)). For each of the `m-1` horizontal cuts, we iterate through `m*n` elements. For each of the `n-1` vertical cuts, we also iterate through `m*n` elements, leading to a high time complexity. · **Space:** O(1). We only use a few variables to store the sums, not counting the input grid.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Highly inefficient due to repeated calculations.; Likely to result in a 'Time Limit Exceeded' error for larger grids.
### Explanation
The algorithm first considers all `m-1` possible horizontal cuts. A horizontal cut can be made between row `i` and row `i+1` for `i` from `0` to `m-2`. For each such cut, we calculate `sum_top`, the sum of all elements from row `0` to `i`, and `sum_bottom`, the sum of all elements from row `i+1` to `m-1`. This requires iterating through all `m*n` cells for each potential cut. If `sum_top` equals `sum_bottom`, a valid partition is found, and we return `true`. If no valid horizontal cut is found, the algorithm proceeds to check all `n-1` possible vertical cuts. A vertical cut can be made between column `j` and `j+1` for `j` from `0` to `n-2`. Similarly, for each vertical cut, we calculate `sum_left` and `sum_right`. If they are equal, we return `true`. If all possible cuts are checked and none result in an equal sum partition, the function returns `false`.

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

        // Check horizontal cuts
        for (int i = 0; i < m - 1; i++) {
            long topSum = 0;
            for (int r = 0; r <= i; r++) {
                for (int c = 0; c < n; c++) {
                    topSum += grid[r][c];
                }
            }

            long bottomSum = 0;
            for (int r = i + 1; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    bottomSum += grid[r][c];
                }
            }

            if (topSum == bottomSum) {
                return true;
            }
        }

        // Check vertical cuts
        for (int j = 0; j < n - 1; j++) {
            long leftSum = 0;
            for (int c = 0; c <= j; c++) {
                for (int r = 0; r < m; r++) {
                    leftSum += grid[r][c];
                }
            }

            long rightSum = 0;
            for (int c = j + 1; c < n; c++) {
                for (int r = 0; r < m; r++) {
                    rightSum += grid[r][c];
                }
            }

            if (leftSum == rightSum) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- Iterate through each possible horizontal cut position `r` from `0` to `m-2`.
- For each `r`, calculate `sum1` (sum of elements in rows `0` to `r`) and `sum2` (sum of elements in rows `r+1` to `m-1`) by iterating through all cells of the grid.
- If `sum1` equals `sum2`, a valid partition is found, so return `true`.
- If no horizontal cut works, iterate through each possible vertical cut position `c` from `0` to `n-2`.
- For each `c`, calculate `sum1` (sum of elements in columns `0` to `c`) and `sum2` (sum of elements in columns `c+1` to `n-1`) by iterating through all cells.
- If `sum1` equals `sum2`, return `true`.
- If no cut is found after checking all possibilities, return `false`.

## Prefix Sum Optimization
This approach significantly improves performance by pre-calculating sums to avoid redundant computations. Instead of recalculating sums for each possible cut, we first compute the sum of each row and each column. This allows us to find the sum of any partition in linear time relative to the dimension of the cut after the initial pre-computation.
**Time:** O(m * n). The initial pass to calculate row and column sums takes `O(m * n)`. The subsequent checks for horizontal and vertical cuts take `O(m)` and `O(n)` respectively. The dominant factor is the initial grid traversal. · **Space:** O(m + n). We use two arrays to store the row and column sums.
**Pros:** Very efficient and optimal for the given constraints.; Avoids re-computation by storing intermediate results (prefix sums).; Includes an early exit condition for grids with an odd total sum.
**Cons:** Requires extra space proportional to the dimensions of the grid.
### Explanation
The core idea is that if a partition into two equal halves is possible, the sum of each half must be `total_sum / 2`. This implies that the `total_sum` of all elements in the grid must be an even number. First, we iterate through the grid once to compute the sum of each row and each column, storing them in `row_sums` and `col_sums` arrays, respectively. During this pass, we also calculate the `total_sum`. If the `total_sum` is odd, we immediately return `false`. We then define the `target_sum` as `total_sum / 2`. Next, we check for a valid horizontal cut by iterating from the first row downwards, accumulating the sum of rows in a `current_sum` variable. If at any point `current_sum` equals `target_sum` before reaching the last row, we've found a valid horizontal cut and return `true`. If no horizontal cut is found, we perform a similar check for vertical cuts by iterating from the first column rightwards. If neither check succeeds, no such partition exists, and we return `false`.

```java
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;

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

        if (totalSum % 2 != 0) {
            return false;
        }

        long targetSum = totalSum / 2;

        // Check for horizontal cuts
        long currentSum = 0;
        for (int i = 0; i < m - 1; i++) {
            currentSum += rowSums[i];
            if (currentSum == targetSum) {
                return true;
            }
        }

        // Check for vertical cuts
        currentSum = 0;
        for (int j = 0; j < n - 1; j++) {
            currentSum += colSums[j];
            if (currentSum == targetSum) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- Create two arrays, `row_sums` of size `m` and `col_sums` of size `n`, initialized to zero.
- Iterate through the `grid` once to populate `row_sums` and `col_sums`, and also calculate the `total_sum` of all elements.
- If `total_sum` is odd, return `false` immediately, as it's impossible to partition into two equal integer sums.
- Calculate the `target_sum = total_sum / 2`.
- Check for horizontal cuts:
  - Initialize `current_sum = 0`.
  - Iterate `i` from `0` to `m-2`.
  - Add `row_sums[i]` to `current_sum`.
  - If `current_sum == target_sum`, return `true`.
- Check for vertical cuts:
  - Initialize `current_sum = 0`.
  - Iterate `j` from `0` to `n-2`.
  - Add `col_sums[j]` to `current_sum`.
  - If `current_sum == target_sum`, return `true`.
- If the loops complete without finding a partition, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean canPartitionGrid(int[][] grid) {
    long s = 0;
    for (var row : grid) {
      for (int x : row) {
        s += x;
      }
    }
    if (s % 2 != 0) {
      return false;
    }
    int m = grid.length, n = grid[0].length;
    long pre = 0;
    for (int i = 0; i < m; ++i) {
      for (int x : grid[i]) {
        pre += x;
      }
      if (pre * 2 == s && i < m - 1) {
        return true;
      }
    }
    pre = 0;
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < m; ++i) {
        pre += grid[i][j];
      }
      if (pre * 2 == s && j < n - 1) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canPartitionGrid(vector<vector<int>> &grid) {
    long long s = 0;
    for (const auto &row : grid) {
      for (int x : row) {
        s += x;
      }
    }
    if (s % 2 != 0) {
      return false;
    }
    int m = grid.size(), n = grid[0].size();
    long long pre = 0;
    for (int i = 0; i < m; ++i) {
      for (int x : grid[i]) {
        pre += x;
      }
      if (pre * 2 == s && i + 1 < m) {
        return true;
      }
    }
    pre = 0;
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < m; ++i) {
        pre += grid[i][j];
      }
      if (pre * 2 == s && j + 1 < n) {
        return true;
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool: s = sum(sum(row) for row in grid) if s % 2: return False pre = 0 for i, row in enumerate(grid): pre += sum(row) if pre * 2 == s and i != len(grid) - 1: return True pre = 0 for j, col in enumerate(zip(* grid)): pre += sum(col) if pre * 2 == s and j != len(grid[0]) - 1: return True return False

```