3548. Equal Sum Grid Partition II

HardArrayHash TableEnumerationMatrixPrefix Sum

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an m x n matrix grid filled with positive integers. Your goal is to figure out whether you can make a single straight cut on the grid—either one horizontal cut or one vertical cut—so that the grid is divided into two pieces satisfying a set of conditions.

When you make a cut, think of it as drawing a line that completely separates the grid into two parts:

A horizontal cut splits the grid between two rows, producing a top section and a bottom section.
A vertical cut splits the grid between two columns, producing a left section and a right section.

After making the cut, the two resulting sections must satisfy all of the following rules:

Both sections must be non-empty. This means you cannot cut along the very edge of the grid; each side must contain at least one full row (for a horizontal cut) or at least one full column (for a vertical cut).
The sums must match (with one allowed exception). Let the sum of all elements in one section be compared with the sum of all elements in the other section. The cut is valid if either:
- The two sums are already equal, or
- You are allowed to discount at most one single cell (from either of the two sections) so that the remaining sums become equal. In other words, you may remove the value of one cell from one of the sections, and after that removal, the two sums should be equal.
Connectivity after discounting. If you choose to discount a cell, the section it was removed from must stay connected. A section is connected when every remaining cell can be reached from any other remaining cell by moving up, down, left, or right through cells that are still in that section. Removing a cell from a corner or edge typically keeps the section connected, but removing an interior cell could break it apart, which is not allowed.

Your task is to return true if there exists at least one valid cut (horizontal or vertical) that meets all of the above conditions, and false otherwise.

Note: The discount counts as at most one cell in total, meaning across both sections combined you may skip the value of a single cell, not one per section.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sums?

This problem maps to Prefix Sums through a short path in the full flowchart.

The problem sweeps through cut positions on the grid, tracking running sums of the top and bottom sections via prefix sum updates to check for equal-sum partitions.

Open in Flowchart

Intuition

The key observation is that a cut is always a full straight line—it goes all the way across the grid. This means the number of possible cuts is small: for a horizontal cut, we only have m - 1 places to cut (between each pair of adjacent rows), and for a vertical cut, we only have n - 1 places. So instead of guessing, we can simply try every possible cut and check whether any of them works.

Let's focus on horizontal cuts first. Imagine sweeping a cut line from top to bottom. As the line moves down by one row, the top section grows by that row, and the bottom section shrinks by that row. This suggests we can keep a running sum of the two parts: start with everything in the bottom, then move rows one at a time into the top. At each step we know s1 (top sum) and s2 (bottom sum) instantly, without recomputing from scratch.

Now, for each cut position we need to answer the partition question. There are two easy cases and one tricky case:

If s1 == s2, the two halves already match, so we return true right away.
If they differ, let diff be the absolute difference. To fix this gap by discounting one cell, that cell must come from the larger section, and its value must be exactly diff. Removing a cell of value diff from the bigger side lowers its sum by diff, making the two sides equal.

To check "does the larger section contain a cell with value diff?" quickly, we maintain two hash maps (cnt1 and cnt2) that count how many times each value appears in the top and bottom parts. As rows move from bottom to top, we update both counts. This lets us test for the existence of a diff-valued cell in O(1).

But existence alone isn't enough—rule 3 demands the section stays connected after the removal. A cell can be safely removed without breaking connectivity only when:

The section has more than one row and more than one column, so it's a "thick" rectangle. Removing any single interior or edge cell from such a block never disconnects it (the surrounding cells still link up).
The section is a single row, and the removed cell sits at one of the two ends (first or last column). Removing an end keeps the rest in one piece, but removing a middle cell would split the row into two.
The section is a single column (width 1), and the removed cell is at the top or bottom end. Same reasoning as the single-row case.

These conditions are exactly what the code checks when it finds a diff-valued cell: it verifies the shape of the larger section and where a removable cell could sit.

Finally, to handle vertical cuts without writing a second nearly identical function, we use a clever trick: transpose the grid (swap rows and columns). A vertical cut on the original grid becomes a horizontal cut on the transposed grid. So we just run the same check function twice—once on grid and once on its transpose zip(*grid)—and return true if either one succeeds.

Pattern Learn more about Prefix Sum patterns.

Solution Approach

The implementation follows the enumerate partition lines method, combined with prefix sums and hash maps for fast lookups. Let's walk through it piece by piece.

The `check` helper

The whole logic for horizontal cuts is wrapped in a helper function check(g). Since vertical cuts can be turned into horizontal cuts by transposing, this single function handles both cases.

def check(g: List[List[int]]) -> bool:
    m, n = len(g), len(g[0])
    s1 = s2 = 0
    cnt1 = defaultdict(int)
    cnt2 = defaultdict(int)

s1 and s2 are the running sums of the top and bottom sections.
cnt1 and cnt2 are hash maps counting how many times each value appears in the top and bottom sections, used for O(1) existence checks.

Initializing the bottom section

We start with everything in the bottom, so s1 = 0 and s2 holds the total of all cells. We also fill cnt2 with the count of every value:

for i, row in enumerate(g):
    for j, x in enumerate(row):
        s2 += x
        cnt2[x] += 1

Sweeping the cut line downward

Now we move rows one at a time from the bottom into the top. We only iterate over the first m - 1 rows (g[: m - 1]), because the cut must leave at least one row in the bottom—both sections must be non-empty.

for i, row in enumerate(g[: m - 1]):
    for x in row:
        s1 += x
        s2 -= x
        cnt1[x] += 1
        cnt2[x] -= 1

After processing row i, the top section contains rows 0..i and the bottom contains rows i+1..m-1. The sums and counts are kept in sync incrementally.

Checking each cut position

First, the easy case—if the two sums already match, we're done:

if s1 == s2:
    return True

Otherwise, we look at which side is larger and compute the difference diff. The cell we discount must come from the larger side and have value exactly diff.

When the bottom is larger (s1 < s2):

diff = s2 - s1
if cnt2[diff]:
    if (
        (m - i - 1 > 1 and n > 1)
        or (i == m - 2 and (g[i + 1][0] == diff or g[i + 1][-1] == diff))
        or (n == 1 and (g[i + 1][0] == diff or g[-1][0] == diff))
    ):
        return True

Here cnt2[diff] checks whether a cell of value diff exists in the bottom. The three connectivity conditions correspond exactly to the shapes discussed:

m - i - 1 > 1 and n > 1: the bottom section has more than one row and more than one column—a thick rectangle, so any cell can be removed safely.
i == m - 2 and (...): the bottom is a single row (g[i+1]), so the removable cell must be at an end—the first column g[i+1][0] or last column g[i+1][-1].
n == 1 and (...): the bottom is a single column, so the removable cell must be at the top end g[i+1][0] or the bottom end g[-1][0].

When the top is larger (s1 > s2):

else:
    diff = s1 - s2
    if cnt1[diff]:
        if (
            (i + 1 > 1 and n > 1)
            or (i == 0 and (g[0][0] == diff or g[0][-1] == diff))
            or (n == 1 and (g[0][0] == diff or g[i][0] == diff))
        ):
            return True

This mirrors the previous case for the top section:

i + 1 > 1 and n > 1: the top has more than one row (rows 0..i) and more than one column.
i == 0 and (...): the top is a single row g[0], so removal must be at an end.
n == 1 and (...): the top is a single column, so removal must be at the top end g[0][0] or bottom end g[i][0].

If no cut position works, the helper returns False.

Handling vertical cuts via transpose

Finally, the main function runs check twice:

return check(grid) or check(list(zip(*grid)))

check(grid) tries all horizontal cuts.
check(list(zip(*grid))) transposes the grid, turning vertical cuts into horizontal ones, then reuses the same logic.

If either returns True, a valid partition exists.

Complexity

Time complexity: O(m × n). Each call to check does a constant amount of work per cell (one initialization pass and one sweep pass), and we call it twice. The transpose also costs O(m × n).
Space complexity: O(m × n) in the worst case, dominated by the hash maps cnt1 and cnt2 storing value counts, plus the transposed grid.

Example Walkthrough

Let's trace through the solution with a small grid where a horizontal cut with a single discounted cell makes the partition work.

grid = [[1, 4],
        [2, 3],
        [5, 1]]

This is a 3 x 2 grid (m = 3, n = 2). The total sum of all cells is 1 + 4 + 2 + 3 + 5 + 1 = 16.

We call check(grid) to try all horizontal cuts.

Step 1: Initialize the bottom section

Everything starts in the bottom, so s1 = 0 and s2 = 16. We also fill cnt2 with every value's count:

cnt2 = {1: 2, 4: 1, 2: 1, 3: 1, 5: 1}
s1 = 0, s2 = 16

Step 2: Sweep the cut line — move row 0 (`[1, 4]`) into the top

We iterate over the first m - 1 = 2 rows. After moving row 0:

s1 = 0 + 1 + 4 = 5
s2 = 16 - 1 - 4 = 7
cnt1 = {1: 1, 4: 1}
cnt2 = {1: 1, 2: 1, 3: 1, 5: 1}   (the 4 dropped to 0)

Now the cut sits between row 0 and row 1:

Top = [[1, 4]] (rows 0)
Bottom = [[2, 3], [5, 1]] (rows 1..2)

Check this cut position (i = 0):

s1 == s2? 5 == 7 → no.
Bottom is larger (s1 < s2), so diff = s2 - s1 = 2.
Does a cell of value 2 exist in the bottom? cnt2[2] = 1 → yes.
Now verify connectivity. The bottom section is rows 1..2, which has m - i - 1 = 2 rows and n = 2 columns.
- Condition m - i - 1 > 1 and n > 1 → 2 > 1 and 2 > 1 → True (a thick rectangle).

The cut succeeds. Removing the cell with value 2 (at position grid[1][0]) from the bottom leaves:

Bottom after discount = [[_, 3], [5, 1]]  → sum = 3 + 5 + 1 = 9...

Wait — let's recheck the arithmetic. The discount must equalize the two sides:

Top sum = 5, Bottom sum = 7, diff = 2.
Remove the value-2 cell from the bottom: new bottom sum = 7 - 2 = 5.
Now Top = 5, Bottom = 5 → equal. ✓

The bottom still forms a connected shape (a 2 x 2 block missing one corner cell stays connected), so all rules are satisfied. check(grid) returns True, and the overall answer is true.

What if this cut had failed?

For completeness, had we continued to i = 1 (cut between rows 1 and 2):

Top = rows 0..1, sum = 5 + 2 + 3 = 10; Bottom = row 2, sum = 6.
diff = 4. The bottom is a single row [5, 1], with no cell of value 4, so cnt1[4]/cnt2[4] lookups fail this position.

And vertical cuts would be tried via check(list(zip(*grid))), transposing the grid into:

[[1, 2, 5],
 [4, 3, 1]]

so a vertical cut on the original becomes a horizontal sweep here — handled by the exact same logic.

Since a valid horizontal cut was already found at i = 0, the function short-circuits and returns true.

Solution Implementation

1from typing import List
2from collections import defaultdict
3
4
5class Solution:
6    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
7        # Try to find a valid horizontal cut in the given grid.
8        # A horizontal cut splits the grid into a top part (first k rows)
9        # and a bottom part (remaining rows). The cut is valid if the two
10        # parts have equal sums, OR if removing exactly one element equal to
11        # the difference (from the heavier part) balances the two parts.
12        def check(g: List[List[int]]) -> bool:
13            rows, cols = len(g), len(g[0])
14
15            top_sum = bottom_sum = 0
16            # Frequency of values currently in the top / bottom parts.
17            top_count = defaultdict(int)
18            bottom_count = defaultdict(int)
19
20            # Initially, everything belongs to the bottom part.
21            for row in g:
22                for value in row:
23                    bottom_sum += value
24                    bottom_count[value] += 1
25
26            # Move rows one by one from the bottom part to the top part.
27            # After processing row i, the top part is rows [0..i] and the
28            # bottom part is rows [i+1..rows-1].
29            for i in range(rows - 1):
30                for value in g[i]:
31                    top_sum += value
32                    bottom_sum -= value
33                    top_count[value] += 1
34                    bottom_count[value] -= 1
35
36                # Case 1: the two parts already have equal sums.
37                if top_sum == bottom_sum:
38                    return True
39
40                # Case 2: the bottom part is heavier. We may remove one
41                # element equal to `diff` from the bottom part to balance.
42                if top_sum < bottom_sum:
43                    diff = bottom_sum - top_sum
44                    if bottom_count[diff]:
45                        # The removed element must be at a "corner-removable"
46                        # position so that both parts stay non-empty/valid:
47                        # - bottom part has at least 2 rows and grid wider than 1
48                        #   column (an interior element can be removed), or
49                        # - bottom part is exactly the last row and the element
50                        #   is at one of its two ends, or
51                        # - the grid has a single column and the element is at
52                        #   the top or bottom end of the bottom part.
53                        if (
54                            (rows - i - 1 > 1 and cols > 1)
55                            or (
56                                i == rows - 2
57                                and (g[i + 1][0] == diff or g[i + 1][-1] == diff)
58                            )
59                            or (cols == 1 and (g[i + 1][0] == diff or g[-1][0] == diff))
60                        ):
61                            return True
62                # Case 3: the top part is heavier. Symmetric to case 2;
63                # we may remove one element equal to `diff` from the top part.
64                else:
65                    diff = top_sum - bottom_sum
66                    if top_count[diff]:
67                        if (
68                            (i + 1 > 1 and cols > 1)
69                            or (i == 0 and (g[0][0] == diff or g[0][-1] == diff))
70                            or (cols == 1 and (g[0][0] == diff or g[i][0] == diff))
71                        ):
72                            return True
73            return False
74
75        # Check horizontal cuts on the original grid, then check vertical cuts
76        # by transposing the grid and reusing the same horizontal-cut logic.
77        return check(grid) or check([list(row) for row in zip(*grid)])
78

1class Solution {
2    /**
3     * Determines whether the grid can be partitioned into two parts with equal sums,
4     * where one part may have a single cell removed to balance the difference.
5     * Checks both horizontal cuts (original grid) and vertical cuts (rotated grid).
6     */
7    public boolean canPartitionGrid(int[][] grid) {
8        return check(grid) || check(rotate(grid));
9    }
10
11    /**
12     * Attempts to find a valid horizontal partition line in the given grid.
13     * The top part accumulates rows from the top; the bottom part holds the rest.
14     * A partition is valid if the two parts have equal sums, or if removing one
15     * eligible cell from the larger part makes the sums equal.
16     */
17    private boolean check(int[][] grid) {
18        int rows = grid.length, cols = grid[0].length;
19        long topSum = 0, bottomSum = 0;
20
21        // Frequency maps tracking how many times each value appears in each part.
22        Map<Long, Integer> topCount = new HashMap<>();
23        Map<Long, Integer> bottomCount = new HashMap<>();
24
25        // Initially all cells belong to the bottom part.
26        for (int[] row : grid) {
27            for (int value : row) {
28                bottomSum += value;
29                bottomCount.merge((long) value, 1, Integer::sum);
30            }
31        }
32
33        // Move rows one by one from the bottom part to the top part,
34        // simulating every possible horizontal cut between rows.
35        for (int i = 0; i < rows - 1; i++) {
36            for (int value : grid[i]) {
37                topSum += value;
38                bottomSum -= value;
39
40                topCount.merge((long) value, 1, Integer::sum);
41                bottomCount.merge((long) value, -1, Integer::sum);
42            }
43
44            // Case 1: the two parts already have equal sums.
45            if (topSum == bottomSum) {
46                return true;
47            }
48
49            if (topSum < bottomSum) {
50                // The bottom part is larger; try removing one cell from it
51                // whose value equals the difference.
52                long diff = bottomSum - topSum;
53                if (bottomCount.getOrDefault(diff, 0) > 0) {
54                    // The removable cell must be a valid corner/edge cell so that
55                    // the remaining bottom part still forms a contiguous region.
56                    boolean bottomHasMultipleRows = rows - i - 1 > 1 && cols > 1;
57                    boolean lastRowCornerRemovable = i == rows - 2
58                            && (grid[i + 1][0] == diff || grid[i + 1][cols - 1] == diff);
59                    boolean singleColumnEndRemovable = cols == 1
60                            && (grid[i + 1][0] == diff || grid[rows - 1][0] == diff);
61
62                    if (bottomHasMultipleRows || lastRowCornerRemovable || singleColumnEndRemovable) {
63                        return true;
64                    }
65                }
66            } else {
67                // The top part is larger; try removing one cell from it
68                // whose value equals the difference.
69                long diff = topSum - bottomSum;
70                if (topCount.getOrDefault(diff, 0) > 0) {
71                    // The removable cell must be a valid corner/edge cell so that
72                    // the remaining top part still forms a contiguous region.
73                    boolean topHasMultipleRows = i + 1 > 1 && cols > 1;
74                    boolean firstRowCornerRemovable = i == 0
75                            && (grid[0][0] == diff || grid[0][cols - 1] == diff);
76                    boolean singleColumnEndRemovable = cols == 1
77                            && (grid[0][0] == diff || grid[i][0] == diff);
78
79                    if (topHasMultipleRows || firstRowCornerRemovable || singleColumnEndRemovable) {
80                        return true;
81                    }
82                }
83            }
84        }
85
86        return false;
87    }
88
89    /**
90     * Returns the transpose of the grid, converting an m x n grid into an n x m grid.
91     * This allows the horizontal-cut logic in check() to also cover vertical cuts.
92     */
93    private int[][] rotate(int[][] grid) {
94        int rows = grid.length, cols = grid[0].length;
95        int[][] transposed = new int[cols][rows];
96        for (int i = 0; i < rows; i++) {
97            for (int j = 0; j < cols; j++) {
98                transposed[j][i] = grid[i][j];
99            }
100        }
101        return transposed;
102    }
103}
104

1class Solution {
2public:
3    bool canPartitionGrid(vector<vector<int>>& grid) {
4        // Check both the original grid (horizontal cuts) and its
5        // transpose (which turns vertical cuts into horizontal ones).
6        return check(grid) || check(rotate(grid));
7    }
8
9private:
10    // Try to split the grid by a horizontal cut so that the two parts
11    // have equal sums, possibly after removing exactly one extra cell
12    // whose value equals the difference between the two parts.
13    bool check(const vector<vector<int>>& g) {
14        int rows = g.size();
15        int cols = g[0].size();
16
17        long long topSum = 0;     // sum of the rows above the cut
18        long long bottomSum = 0;  // sum of the rows below the cut
19
20        // Frequency of each value in the top part and bottom part.
21        unordered_map<long long, int> topCount;
22        unordered_map<long long, int> bottomCount;
23
24        // Initially everything belongs to the bottom part.
25        for (const auto& row : g) {
26            for (int value : row) {
27                bottomSum += value;
28                bottomCount[value]++;
29            }
30        }
31
32        // Move rows one by one from the bottom part to the top part,
33        // simulating every possible horizontal cut position.
34        for (int i = 0; i < rows - 1; i++) {
35            for (int value : g[i]) {
36                topSum += value;
37                bottomSum -= value;
38                topCount[value]++;
39                bottomCount[value]--;
40            }
41
42            // Case 1: the two parts already have equal sums.
43            if (topSum == bottomSum) {
44                return true;
45            }
46
47            if (topSum < bottomSum) {
48                // The bottom part is heavier; we may remove one cell from
49                // the bottom whose value equals the difference.
50                long long diff = bottomSum - topSum;
51                if (bottomCount[diff] > 0) {
52                    // The removable cell must be a "corner-removable" cell:
53                    // either the bottom part still has more than one row and
54                    // multiple columns (so a corner can always be peeled off),
55                    // or it is a single remaining row / single column where the
56                    // candidate must sit at one of the exposed ends.
57                    if ((rows - i - 1 > 1 && cols > 1) ||
58                        (i == rows - 2 &&
59                         (g[i + 1][0] == diff || g[i + 1][cols - 1] == diff)) ||
60                        (cols == 1 &&
61                         (g[i + 1][0] == diff || g[rows - 1][0] == diff))) {
62                        return true;
63                    }
64                }
65            } else {
66                // The top part is heavier; we may remove one cell from
67                // the top whose value equals the difference.
68                long long diff = topSum - bottomSum;
69                if (topCount[diff] > 0) {
70                    // Same corner-removable reasoning applied to the top part.
71                    if ((i + 1 > 1 && cols > 1) ||
72                        (i == 0 &&
73                         (g[0][0] == diff || g[0][cols - 1] == diff)) ||
74                        (cols == 1 &&
75                         (g[0][0] == diff || g[i][0] == diff))) {
76                        return true;
77                    }
78                }
79            }
80        }
81
82        return false;
83    }
84
85    // Build the transpose of the grid so vertical cuts can be checked
86    // with the same horizontal-cut logic.
87    vector<vector<int>> rotate(vector<vector<int>>& grid) {
88        int rows = grid.size();
89        int cols = grid[0].size();
90        vector<vector<int>> transposed(cols, vector<int>(rows));
91        for (int i = 0; i < rows; i++) {
92            for (int j = 0; j < cols; j++) {
93                transposed[j][i] = grid[i][j];
94            }
95        }
96        return transposed;
97    }
98};
99

1/**
2 * Determines whether the grid can be partitioned into two parts with equal sums.
3 * A valid partition can be made either by a horizontal cut on the original grid,
4 * or by a horizontal cut on the rotated (transposed) grid (which simulates a vertical cut).
5 *
6 * @param grid - The input 2D number grid.
7 * @returns True if a valid equal-sum partition exists; otherwise false.
8 */
9function canPartitionGrid(grid: number[][]): boolean {
10    return check(grid) || check(rotate(grid));
11}
12
13/**
14 * Checks whether a horizontal cut can split the grid into a top part and a bottom part
15 * with equal sums, allowing the removal of a single matching corner-accessible cell to
16 * balance the difference.
17 *
18 * @param matrix - The grid to check.
19 * @returns True if a valid horizontal partition exists; otherwise false.
20 */
21function check(matrix: number[][]): boolean {
22    const rows = matrix.length;
23    const cols = matrix[0].length;
24
25    // topSum holds the running sum of the upper part,
26    // bottomSum holds the running sum of the lower part.
27    let topSum = 0;
28    let bottomSum = 0;
29
30    // Frequency maps tracking value counts in the top and bottom parts.
31    const topCount = new Map<number, number>();
32    const bottomCount = new Map<number, number>();
33
34    // Initialize the bottom part with all cells of the grid.
35    for (const row of matrix) {
36        for (const value of row) {
37            bottomSum += value;
38            bottomCount.set(value, (bottomCount.get(value) || 0) + 1);
39        }
40    }
41
42    // Try every horizontal cut position (after row i, for i from 0 to rows - 2).
43    for (let i = 0; i < rows - 1; i++) {
44        // Move row i from the bottom part to the top part.
45        for (const value of matrix[i]) {
46            topSum += value;
47            bottomSum -= value;
48
49            topCount.set(value, (topCount.get(value) || 0) + 1);
50            bottomCount.set(value, (bottomCount.get(value) || 0) - 1);
51        }
52
53        // Case 1: The two parts already have equal sums.
54        if (topSum === bottomSum) return true;
55
56        if (topSum < bottomSum) {
57            // The bottom part is heavier; we may remove one cell of value `diff`
58            // from the bottom to balance the two parts.
59            const diff = bottomSum - topSum;
60            if ((bottomCount.get(diff) || 0) > 0) {
61                if (
62                    // The bottom part has more than one row and more than one column,
63                    // so a removable cell can always be positioned at a corner.
64                    (rows - i - 1 > 1 && cols > 1) ||
65                    // The bottom part is exactly one row; the removable cell must be at an end.
66                    (i === rows - 2 &&
67                        (matrix[i + 1][0] === diff || matrix[i + 1][cols - 1] === diff)) ||
68                    // The grid is a single column; the removable cell must be at an end.
69                    (cols === 1 &&
70                        (matrix[i + 1][0] === diff || matrix[rows - 1][0] === diff))
71                )
72                    return true;
73            }
74        } else {
75            // The top part is heavier; we may remove one cell of value `diff`
76            // from the top to balance the two parts.
77            const diff = topSum - bottomSum;
78            if ((topCount.get(diff) || 0) > 0) {
79                if (
80                    // The top part has more than one row and more than one column,
81                    // so a removable cell can always be positioned at a corner.
82                    (i + 1 > 1 && cols > 1) ||
83                    // The top part is exactly one row; the removable cell must be at an end.
84                    (i === 0 && (matrix[0][0] === diff || matrix[0][cols - 1] === diff)) ||
85                    // The grid is a single column; the removable cell must be at an end.
86                    (cols === 1 && (matrix[0][0] === diff || matrix[i][0] === diff))
87                )
88                    return true;
89            }
90        }
91    }
92
93    return false;
94}
95
96/**
97 * Rotates (transposes) the grid so that columns become rows.
98 * This allows the horizontal-cut logic in `check` to handle vertical cuts as well.
99 *
100 * @param grid - The input grid.
101 * @returns A new transposed grid.
102 */
103function rotate(grid: number[][]): number[][] {
104    const rows = grid.length;
105    const cols = grid[0].length;
106
107    // Create a transposed grid with swapped dimensions.
108    const transposed: number[][] = Array.from({ length: cols }, () => Array(rows).fill(0));
109
110    for (let i = 0; i < rows; i++) {
111        for (let j = 0; j < cols; j++) {
112            transposed[j][i] = grid[i][j];
113        }
114    }
115
116    return transposed;
117}
118

Time and Space Complexity

Time Complexity: O(m × n), where m and n are the number of rows and columns of the matrix, respectively. The function check performs two passes over the grid: the first nested loop iterates over all m × n elements to compute the total sum s2 and build the count dictionary cnt2, taking O(m × n) time. The second loop iterates over the first m - 1 rows, processing each element once to update s1, s2, cnt1, and cnt2, also taking O(m × n) time; the constant-time boundary checks inside add no extra cost. The check function is invoked twice — once on the original grid and once on its transpose list(zip(*grid)). Transposing also costs O(m × n). Hence the overall time complexity remains O(m × n).
Space Complexity: O(m × n), where m and n are the number of rows and columns of the matrix, respectively. The dominant space usage comes from the dictionaries cnt1 and cnt2, which in the worst case store up to O(m × n) distinct values, and from constructing the transposed grid list(zip(*grid)), which occupies O(m × n) space.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misjudging Connectivity When Discounting an Interior Cell

The most subtle and error-prone part of this problem is rule 3—after discounting a cell, the section it was removed from must stay connected. A naive implementation simply checks whether a cell of value diff exists in the heavier section and immediately returns True:

# WRONG: ignores connectivity entirely
diff = bottom_sum - top_sum
if bottom_count[diff]:
    return True

This is incorrect because removing an interior cell from a section can split it into two disconnected pieces. For example, in a "plus"-shaped or single-row-with-a-hole layout, deleting the middle cell breaks the path between its left and right neighbors, violating the rule. The check above would wrongly accept such a cut.

Why the correct code works: The key insight is reasoning about which cells are always safe to remove rather than running an expensive connectivity test for every candidate cell:

If a section has more than one row AND more than one column (rows - i - 1 > 1 and cols > 1), it is a "thick" rectangle. Removing any single cell from a rectangle of size ≥ 2×2 always leaves it connected, so we don't even need to check which cell—existence of value diff is enough.
If the section is a single row, only the two end cells can be removed safely; removing a middle cell splits the row. Hence we must verify g[i+1][0] == diff or g[i+1][-1] == diff.
If the grid is a single column, the same logic applies vertically—only the top/bottom ends are safe.

Takeaway: Don't reach for a generic BFS/DFS connectivity check per candidate; instead, classify the section's shape (thick rectangle vs. single line) and apply the corresponding rule. This keeps the algorithm at O(m × n) instead of degrading to O((m × n)²).

Pitfall 2: Forgetting That the Discount Is "At Most One Cell Total"

A second common mistake is treating the discount as one cell per section rather than one cell across both sections combined. The correct logic always removes the cell from the heavier side with value exactly equal to the difference:

diff = bottom_sum - top_sum   # the gap to close
if bottom_count[diff]:         # cell must live in the heavier (bottom) side
    ...

Removing a cell of value diff from the heavier side closes the gap exactly. Trying to remove a cell from the lighter side, or attempting two removals, both violate the problem's constraint and lead to wrong answers. Always anchor on: which side is bigger, and does it contain a single cell equal to the surplus?

Pitfall 3: Off-By-One Errors on the "Both Sections Non-Empty" Rule

The loop runs for i in range(rows - 1) rather than range(rows). Iterating up to rows - 1 ensures the bottom always retains at least one row, satisfying rule 1 (both sections non-empty). A frequent bug is writing range(rows), which allows a "cut" that leaves the bottom empty—an invalid partition that should never be considered. When adapting this pattern, double-check that the sweep stops one position before the last row/column.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: