3548. Equal Sum Grid Partition II
Hard
50 Points
Array
Hash Table
Matrix
Enumeration
Prefix Sum
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.
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
Input: grid = [[1,4],[2,3]]
Output: true
Explanation:
Example 2
Input: grid = [[1,2],[3,4]]
Output: true
Explanation:
Example 3
Input: grid = [[1,2,4],[2,3,5]]
Output: false
Explanation:
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 <= 1051 <= n == grid[i].length <= 1052 <= m * n <= 1051 <= grid[i][j] <= 105
3548. Equal Sum Grid Partition II
Hard
50 Points
Array
Hash Table
Matrix
Enumeration
Prefix Sum
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.
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
Input: grid = [[1,4],[2,3]]
Output: true
Explanation:
Example 2
Input: grid = [[1,2],[3,4]]
Output: true
Explanation:
Example 3
Input: grid = [[1,2,4],[2,3,5]]
Output: false
Explanation:
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 <= 1051 <= n == grid[i].length <= 1052 <= m * n <= 1051 <= grid[i][j] <= 105