1230. Four-Way Fair Cut
A land registry stores plot values in a rectangular grid. An inspector may cut the land once horizontally and once vertically. A cut (r, c) with 1 <= r < rows and 1 <= c < cols separates the grid into four non-empty quadrants: rows below r or at least r, combined with columns below c or at least c.
A cut is fair when all four quadrants have exactly the same sum of values. Return the number of fair cuts. Values can be negative or zero, so a quadrant sum may be any integer.
Build a 2-D prefix sum so every quadrant sum takes O(1) and test all cuts. Time O(rows * cols), space O(rows * cols).
Example 1
- Input:
- grid = [[4,-2,3,7,-1],[1,0,4,2,2],[6,2,2,9,0],[-3,5,-2,-4,5]]
- Output:
- 1
- Explanation:
Cutting after row 2 and column 3 gives four quadrants that each sum to 10, and no other cut balances all four.
Example 2
- Input:
- grid = [[2,8,1],[5,-3,4],[9,6,0],[3,3,-2]]
- Output:
- 0
- Explanation:
All 6 possible cuts leave at least two quadrants with different sums, so there are no fair cuts.
Example 3
- Input:
- grid = [[5,5,2,2],[5,5,2,2],[7,7,3,3],[7,7,3,3]]
- Output:
- 0
- Explanation:
The central cut (2, 2) gives quadrant sums 20, 8, 28 and 12, and none of the other 8 cuts balance either, so the answer is 0.
Constraints
2 ≤ rows, cols ≤ 100
-1000 ≤ grid[i][j] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(rows * cols)
- Space
- O(rows * cols)