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.

Examples

Example 1

1
2
3
4
5

Input: grid = [[1,4],[2,3]]
Output: true
Explanation:
![](https://assets.leetcode.com/uploads/2025/03/30/lc.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

1
2
3
4
5
6
7

Input: grid = [[1,2],[3,4]]
Output: true
Explanation:
![](https://assets.leetcode.com/uploads/2025/04/01/chatgpt-image-
apr-1-2025-at-05_28_12-pm.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

1
2
3
4
5
6
7

Input: grid = [[1,2,4],[2,3,5]]
Output: false
Explanation:
**![](https://assets.leetcode.com/uploads/2025/04/01/chatgpt-image-
apr-2-2025-at-02_50_29-am.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

1
2
3
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 <= 10^5
  • 1 <= n == grid[i].length <= 10^5
  • 2 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^5

Solution

Method 1 – Prefix Sum, Cut Check, and Discount Cell Simulation

Intuition

We want to split the grid into two non-empty parts with a single horizontal or vertical cut, such that the sums are equal or can be made equal by discounting at most one cell (removing its value from one part), and the remaining section must stay connected. For each possible cut, check if the sums are equal, or if the difference can be matched by removing a border cell (which keeps the section connected).

Approach

  1. Compute the total sum of the grid.
  2. For each possible horizontal cut (between row i and i+1):
    • Compute the sum of the top and bottom parts.
    • If equal, return true.
    • If not, check if the difference can be matched by removing a cell from the border row (last row of top or first row of bottom), and the section remains connected.
  3. For each possible vertical cut (between column j and j+1):
    • Compute the sum of the left and right parts.
    • If equal, return true.
    • If not, check if the difference can be matched by removing a cell from the border column (last col of left or first col of right), and the section remains connected.
  4. If no such cut exists, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution:
    def isPossibleToCutGrid(self, grid: list[list[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        total = sum(sum(row) for row in grid)
        # Horizontal cuts
        top_sum = 0
        for i in range(m - 1):
            top_sum += sum(grid[i])
            bot_sum = total - top_sum
            if top_sum == bot_sum:
                return True
            diff = abs(top_sum - bot_sum)
            # Try discounting a cell on the border
            if top_sum > bot_sum:
                # Remove from last row of top
                for v in grid[i]:
                    if top_sum - v == bot_sum:
                        return True
            else:
                # Remove from first row of bottom
                for v in grid[i+1]:
                    if bot_sum - v == top_sum:
                        return True
        # Vertical cuts
        left_sum = [0] * n
        for j in range(n - 1):
            for i in range(m):
                left_sum[j] += grid[i][j]
            right_sum = sum(grid[i][j+1] for i in range(m))
            lsum = sum(left_sum[:j+1])
            rsum = total - lsum
            if lsum == rsum:
                return True
            diff = abs(lsum - rsum)
            # Try discounting a cell on the border
            if lsum > rsum:
                for i in range(m):
                    if lsum - grid[i][j] == rsum:
                        return True
            else:
                for i in range(m):
                    if rsum - grid[i][j+1] == lsum:
                        return True
        return False

Complexity

  • ⏰ Time complexity: O(mn), since we may check each border cell for each possible cut.
  • 🧺 Space complexity: O(n) for prefix sums.