Equal Sum Grid Partition II
Intuition #
We want to find a single horizontal or vertical line that splits the grid into two sections with equal sums, allowing us to remove at most one cell to make them equal.
For each possible cut, we track the prefix sum of the top section and derive the bottom section’s sum as total - prefix. If they differ, we need to discard exactly one cell whose value equals the difference. The catch is that the discarded cell must not disconnect its section.
Connectivity is the interesting part. A multi-row (or multi-column) section is always safe (Removing any single cell from a grid-shaped region leaves it connected). But a single-row section is just a line of cells, so removing anything other than a corner breaks it in two. This gives us a clean rule: if the section has more than one row, any cell with the right value works; if it’s exactly one row, only the two corner cells are valid candidates.
Rather than handling horizontal and vertical cuts separately, we rotate the grid 90 degrees and run the same horizontal-cut logic twice.
Approach #
Ris the length ofgridandCis the length ofgrid[0].
- Compute the total sum of the grid.
- Try a horizontal cut using
canPartition(). If the grid has only one column, delegate tocanPartitionOne()since connectivity rules differ there. - Rotate the grid (transposing rows to columns) and try again (this covers vertical cuts).
- In
canPartition():- Build a prefix sum over row sums to efficiently compute the top/bottom section sums at each cut position.
- Maintain
topCountandbottomCountfrequency maps to track which values are available for discounting. - At each cut i (splitting rows
0..i-1into top,i..R-1into bottom):- If
sums == equal: returntrueimmediately. - If
top > bottom: we need to removewanted = prefix - (total - prefix)from the top. If the top is only one row (i == 1), only the two corner cellsgrid[0][0]andgrid[0][C-1]can be removed safely. Otherwise, any cell in the top works (grid stays connected). - Symmetric logic for
bottom > top: we need to removetotal - prefix - prefixfrom the bottom. If the bottom is only one row (i == R-1), only the two corner cellsgrid[R-1][0]andgrid[R-1][C-1]can be removed safely. Otherwise, any cell in the bottom works (grid stays connected).
- If
canPartitionOne()handles the single-column edge case: here, removing any non-endpoint cell from a section would disconnect it, so only the global top (grid[0][0]), global bottom (grid[R-1][0]), or the two cells directly adjacent to the cut are valid candidates.
Complexity #
Time complexity:
- We iterate over all cells a constant number of times (sum, rotate, prefix sums, count maps).
Space complexity:
- For the rotated grid and the frequency maps.
Code #
1func canPartitionGrid(grid [][]int) bool {
2 total := 0
3 for _, row := range grid {
4 for _, num := range row {
5 total += num
6 }
7 }
8
9 // Trying horizontal cut at first, then
10 // trying vertical cut by rotating the
11 // grid.
12 if len(grid) != 1 && canPartition(grid, total) {
13 return true
14 }
15
16 rotatedGrid := rotate(grid)
17 return canPartition(rotatedGrid, total)
18}
19
20func canPartition(grid [][]int, total int) bool {
21 R, C := len(grid), len(grid[0])
22
23 if C == 1 {
24 return canPartitionOne(grid, total)
25 }
26
27 // Saving count for each number
28 bottomCount := make(map[int]int)
29 for _, row := range grid {
30 for _, num := range row {
31 bottomCount[num]++
32 }
33 }
34
35 // Creating Prefix Sum of the Rows
36 nums := make([]int, R)
37 for y, row := range grid {
38 sum := 0
39 for _, num := range row {
40 sum += num
41 }
42 nums[y] = sum
43 }
44
45 topCount := make(map[int]int)
46 prefix := 0
47 for i := 1; i < R; i++ { // Cut begins from 1 until R-1 inclusive
48 prefix += nums[i-1]
49
50 // Decreasing number count in bottomCount
51 // and increasing in topCount, as the cut
52 // is going down.
53 for _, num := range grid[i-1] {
54 bottomCount[num]--
55 topCount[num]++
56 }
57
58 if diff := total - prefix; diff == prefix { // No need for discounting a number
59 return true
60 } else if diff < prefix { // Discount from the top
61 wanted := prefix - (total - prefix)
62 if i == 1 { // We are having a cut before 1
63 // We can only remove the top edges grid[0][0] and grid[0][C-1]
64 if wanted == grid[0][0] || wanted == grid[0][C-1] {
65 return true
66 }
67 } else if topCount[wanted] > 0 { // Removing from top
68 return true
69 }
70 } else if diff > prefix { // Discount from the bottom
71 wanted := total - prefix - prefix
72 if i == R-1 { // We are having a cut before R-2
73 // We can only remove the bottom edges grid[R-1][0] and grid[R-1][C-1]
74 if wanted == grid[R-1][0] || wanted == grid[R-1][C-1] {
75 return true
76 }
77 } else if bottomCount[wanted] > 0 { // Removing from bottom
78 return true
79 }
80 }
81 }
82
83 return false
84}
85
86func canPartitionOne(grid [][]int, total int) bool {
87 // Grid with one column
88 // We can remove either the top, the bottom,
89 // or the before/after the cut.
90 R := len(grid)
91
92 prefix := 0
93 for y := 1; y < R; y++ {
94 prefix += grid[y-1][0]
95
96 if diff := total - prefix; diff == prefix {
97 return true
98 } else {
99 var wanted int
100 if diff < prefix {
101 wanted = prefix - (total - prefix)
102 } else if diff > prefix {
103 wanted = total - prefix - prefix
104 }
105
106 if wanted == grid[0][0] || wanted == grid[R-1][0] {
107 return true
108 }
109
110 if wanted == grid[y][0] || wanted == grid[y-1][0] {
111 return true
112 }
113 }
114 }
115
116 return false
117}
118
119func rotate(grid [][]int) [][]int {
120 R, C := len(grid), len(grid[0])
121
122 result := make([][]int, C)
123 for y := range result {
124 result[y] = make([]int, R)
125 }
126
127 for y, row := range grid {
128 for x, num := range row {
129 result[x][R-1-y] = num
130 }
131 }
132
133 return result
134}