Equal Sum Grid Partition II
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
1 4 2 3
Input
grid = [[1,4],[2,3]]Output
trueA horizontal cut after the first row gives sums 5 and 5, which are equal.
Example 2
1 2 3 4
Input
grid = [[1,2],[3,4]]Output
trueA vertical cut after the first column gives sums 4 and 6, and discounting 2 from the right section makes both sums equal while keeping the section connected.
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