Skip to content

3548. Equal Sum Grid Partition II

Description

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:

Input: grid = [[1,4],[2,3]]

Output: true

Explanation:

  • A horizontal cut after the first row gives sums 1 + 4 = 5 and 2 + 3 = 5, which are equal. Thus, the answer is true.

Example 2:

Input: grid = [[1,2],[3,4]]

Output: true

Explanation:

  • A vertical cut after the first column gives sums 1 + 3 = 4 and 2 + 4 = 6.
  • By discounting 2 from the right section (6 - 2 = 4), both sections have equal sums and remain connected. Thus, the answer is true.

Example 3:

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

Output: false

Explanation:

  • A horizontal cut after the first row gives 1 + 2 + 4 = 7 and 2 + 3 + 5 = 10.
  • By discounting 3 from the bottom section (10 - 3 = 7), both sections have equal sums, but they do not remain connected as it splits the bottom section into two parts ([2] and [5]). Thus, the answer is false.

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 <= 105
  • 1 <= n == grid[i].length <= 105
  • 2 <= m * n <= 105
  • 1 <= grid[i][j] <= 105

Solutions

Method 1: Enumerate Partition Lines

We can first enumerate horizontal partition lines, compute the element sum of each resulting part, and use hash maps to record the occurrence count of elements in each part.

For each partition line, we need to determine whether the sums of the two parts are equal, or whether removing one cell can make them equal. If the sums are equal, we directly return \(\text{true}\). If the sums are not equal, we compute their difference \(\textit{diff}\). If \(\textit{diff}\) exists in the hash map of the larger part and satisfies the connectivity condition after removing that cell, we also return \(\text{true}\).

The connectivity condition can be checked using the following criteria:

  • The part has more than \(1\) row and more than \(1\) column.
  • The part has exactly \(1\) row, and the removed cell is on the boundary of that part (i.e., the first column or the last column).
  • The part has exactly \(1\) row, and the removed cell is on the boundary of that part (i.e., the first row or the last row).

Satisfying any one of the above conditions guarantees that the part remains connected after removing the cell.

We also need to enumerate vertical partition lines, which is similar to the horizontal case. To simplify the enumeration of vertical partition lines, we can first transpose the matrix and then apply the same logic.

The time complexity is \(O(m \times n)\) and the space complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns of the matrix, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        def check(g: List[List[int]]) -> bool:
            m, n = len(g), len(g[0])
            s1 = s2 = 0
            cnt1 = defaultdict(int)
            cnt2 = defaultdict(int)
            for i, row in enumerate(g):
                for j, x in enumerate(row):
                    s2 += x
                    cnt2[x] += 1
            for i, row in enumerate(g[: m - 1]):
                for x in row:
                    s1 += x
                    s2 -= x
                    cnt1[x] += 1
                    cnt2[x] -= 1
                if s1 == s2:
                    return True
                if 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
                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
            return False

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        return check(grid) || check(rotate(grid));
    }

    private boolean check(int[][] g) {
        int m = g.length, n = g[0].length;
        long s1 = 0, s2 = 0;

        Map<Long, Integer> cnt1 = new HashMap<>();
        Map<Long, Integer> cnt2 = new HashMap<>();

        for (int[] row : g) {
            for (int x : row) {
                s2 += x;
                cnt2.merge((long) x, 1, Integer::sum);
            }
        }

        for (int i = 0; i < m - 1; i++) {
            for (int x : g[i]) {
                s1 += x;
                s2 -= x;

                cnt1.merge((long) x, 1, Integer::sum);
                cnt2.merge((long) x, -1, Integer::sum);
            }

            if (s1 == s2) {
                return true;
            }

            if (s1 < s2) {
                long diff = s2 - s1;
                if (cnt2.getOrDefault(diff, 0) > 0) {
                    if ((m - i - 1 > 1 && n > 1)
                        || (i == m - 2 && (g[i + 1][0] == diff || g[i + 1][n - 1] == diff))
                        || (n == 1 && (g[i + 1][0] == diff || g[m - 1][0] == diff))) {
                        return true;
                    }
                }
            } else {
                long diff = s1 - s2;
                if (cnt1.getOrDefault(diff, 0) > 0) {
                    if ((i + 1 > 1 && n > 1) || (i == 0 && (g[0][0] == diff || g[0][n - 1] == diff))
                        || (n == 1 && (g[0][0] == diff || g[i][0] == diff))) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    private int[][] rotate(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] t = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                t[j][i] = grid[i][j];
            }
        }
        return t;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        return check(grid) || check(rotate(grid));
    }

private:
    bool check(const vector<vector<int>>& g) {
        int m = g.size(), n = g[0].size();
        long long s1 = 0, s2 = 0;

        unordered_map<long long, int> cnt1, cnt2;

        for (auto& row : g) {
            for (int x : row) {
                s2 += x;
                cnt2[x]++;
            }
        }

        for (int i = 0; i < m - 1; i++) {
            for (int x : g[i]) {
                s1 += x;
                s2 -= x;
                cnt1[x]++;
                cnt2[x]--;
            }

            if (s1 == s2) return true;

            if (s1 < s2) {
                long long diff = s2 - s1;
                if (cnt2[diff] > 0) {
                    if (
                        (m - i - 1 > 1 && n > 1) || (i == m - 2 && (g[i + 1][0] == diff || g[i + 1][n - 1] == diff)) || (n == 1 && (g[i + 1][0] == diff || g[m - 1][0] == diff))) return true;
                }
            } else {
                long long diff = s1 - s2;
                if (cnt1[diff] > 0) {
                    if (
                        (i + 1 > 1 && n > 1) || (i == 0 && (g[0][0] == diff || g[0][n - 1] == diff)) || (n == 1 && (g[0][0] == diff || g[i][0] == diff))) return true;
                }
            }
        }

        return false;
    }

    vector<vector<int>> rotate(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> t(n, vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                t[j][i] = grid[i][j];
            }
        }
        return t;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
func canPartitionGrid(grid [][]int) bool {
    return check(grid) || check(rotate(grid))
}

func check(g [][]int) bool {
    m, n := len(g), len(g[0])
    var s1, s2 int64

    cnt1 := map[int64]int{}
    cnt2 := map[int64]int{}

    for _, row := range g {
        for _, x := range row {
            v := int64(x)
            s2 += v
            cnt2[v]++
        }
    }

    for i := 0; i < m-1; i++ {
        for _, x := range g[i] {
            v := int64(x)
            s1 += v
            s2 -= v
            cnt1[v]++
            cnt2[v]--
        }

        if s1 == s2 {
            return true
        }

        if s1 < s2 {
            diff := s2 - s1
            if cnt2[diff] > 0 {
                if (m-i-1 > 1 && n > 1) ||
                    (i == m-2 && (int64(g[i+1][0]) == diff || int64(g[i+1][n-1]) == diff)) ||
                    (n == 1 && (int64(g[i+1][0]) == diff || int64(g[m-1][0]) == diff)) {
                    return true
                }
            }
        } else {
            diff := s1 - s2
            if cnt1[diff] > 0 {
                if (i+1 > 1 && n > 1) ||
                    (i == 0 && (int64(g[0][0]) == diff || int64(g[0][n-1]) == diff)) ||
                    (n == 1 && (int64(g[0][0]) == diff || int64(g[i][0]) == diff)) {
                    return true
                }
            }
        }
    }

    return false
}

func rotate(grid [][]int) [][]int {
    m, n := len(grid), len(grid[0])
    t := make([][]int, n)
    for i := range t {
        t[i] = make([]int, m)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            t[j][i] = grid[i][j]
        }
    }
    return t
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
function canPartitionGrid(grid: number[][]): boolean {
    return check(grid) || check(rotate(grid));
}

function check(g: number[][]): boolean {
    const m = g.length,
        n = g[0].length;
    let s1 = 0,
        s2 = 0;

    const cnt1 = new Map<number, number>();
    const cnt2 = new Map<number, number>();

    for (const row of g) {
        for (const x of row) {
            s2 += x;
            cnt2.set(x, (cnt2.get(x) || 0) + 1);
        }
    }

    for (let i = 0; i < m - 1; i++) {
        for (const x of g[i]) {
            s1 += x;
            s2 -= x;

            cnt1.set(x, (cnt1.get(x) || 0) + 1);
            cnt2.set(x, (cnt2.get(x) || 0) - 1);
        }

        if (s1 === s2) return true;

        if (s1 < s2) {
            const diff = s2 - s1;
            if ((cnt2.get(diff) || 0) > 0) {
                if (
                    (m - i - 1 > 1 && n > 1) ||
                    (i === m - 2 && (g[i + 1][0] === diff || g[i + 1][n - 1] === diff)) ||
                    (n === 1 && (g[i + 1][0] === diff || g[m - 1][0] === diff))
                )
                    return true;
            }
        } else {
            const diff = s1 - s2;
            if ((cnt1.get(diff) || 0) > 0) {
                if (
                    (i + 1 > 1 && n > 1) ||
                    (i === 0 && (g[0][0] === diff || g[0][n - 1] === diff)) ||
                    (n === 1 && (g[0][0] === diff || g[i][0] === diff))
                )
                    return true;
            }
        }
    }

    return false;
}

function rotate(grid: number[][]): number[][] {
    const m = grid.length,
        n = grid[0].length;
    const t: number[][] = Array.from({ length: n }, () => Array(m).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            t[j][i] = grid[i][j];
        }
    }

    return t;
}

Comments