3546. Equal Sum Grid Partition I

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 the elements in both sections is equal.

Return true if such a partition exists; otherwise return false.

Example 1:

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

Output: true

Explanation:

A horizontal cut between row 0 and row 1 results in two non-empty sections, each with a sum of 5. Thus, the answer is true.

Example 2:

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

Output: false

Explanation:

No horizontal or vertical cut results in two non-empty sections with equal sums. Thus, the answer is false.

Constraints:

1 <= m == grid.length <= 10⁵
1 <= n == grid[i].length <= 10⁵
2 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

Solutions

Solution 1: Enumeration + Prefix Sum

First, we calculate the sum of all elements in the matrix, denoted as \(s\). If \(s\) is odd, it is impossible to divide the matrix into two parts with equal sums, so we directly return false.

If \(s\) is even, we can enumerate all possible partition lines to check if there exists a line that divides the matrix into two parts with equal sums.

We traverse each row from top to bottom, calculating the sum of all elements in the rows above the current row, denoted as \(\textit{pre}\). If \(\textit{pre} \times 2 = s\) and the current row is not the last row, it means we can perform a horizontal partition between the current row and the next row, so we return true.

If no such partition line is found, we traverse each column from left to right, calculating the sum of all elements in the columns to the left of the current column, denoted as \(\textit{pre}\). If \(\textit{pre} \times 2 = s\) and the current column is not the last column, it means we can perform a vertical partition between the current column and the next column, so we return true.

If no such partition line is found, we return false.

The time complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns in the matrix, respectively. The space complexity is \(O(1)\), as only constant extra space is used.

Python3JavaC++GoTypeScript

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        s = sum(sum(row) for row in grid)
        if s % 2:
            return False
        pre = 0
        for i, row in enumerate(grid):
            pre += sum(row)
            if pre * 2 == s and i != len(grid) - 1:
                return True
        pre = 0
        for j, col in enumerate(zip(*grid)):
            pre += sum(col)
            if pre * 2 == s and j != len(grid[0]) - 1:
                return True
        return False

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        long s = 0;
        for (var row : grid) {
            for (int x : row) {
                s += x;
            }
        }
        if (s % 2 != 0) {
            return false;
        }
        int m = grid.length, n = grid[0].length;
        long pre = 0;
        for (int i = 0; i < m; ++i) {
            for (int x : grid[i]) {
                pre += x;
            }
            if (pre * 2 == s && i < m - 1) {
                return true;
            }
        }
        pre = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                pre += grid[i][j];
            }
            if (pre * 2 == s && j < n - 1) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        long long s = 0;
        for (const auto& row : grid) {
            for (int x : row) {
                s += x;
            }
        }
        if (s % 2 != 0) {
            return false;
        }
        int m = grid.size(), n = grid[0].size();
        long long pre = 0;
        for (int i = 0; i < m; ++i) {
            for (int x : grid[i]) {
                pre += x;
            }
            if (pre * 2 == s && i + 1 < m) {
                return true;
            }
        }
        pre = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                pre += grid[i][j];
            }
            if (pre * 2 == s && j + 1 < n) {
                return true;
            }
        }
        return false;
    }
};

func canPartitionGrid(grid [][]int) bool {
    s := 0
    for _, row := range grid {
        for _, x := range row {
            s += x
        }
    }
    if s%2 != 0 {
        return false
    }
    m, n := len(grid), len(grid[0])
    pre := 0
    for i, row := range grid {
        for _, x := range row {
            pre += x
        }
        if pre*2 == s && i+1 < m {
            return true
        }
    }
    pre = 0
    for j := 0; j < n; j++ {
        for i := 0; i < m; i++ {
            pre += grid[i][j]
        }
        if pre*2 == s && j+1 < n {
            return true
        }
    }
    return false
}

function canPartitionGrid(grid: number[][]): boolean {
    let s = 0;
    for (const row of grid) {
        s += row.reduce((a, b) => a + b, 0);
    }
    if (s % 2 !== 0) {
        return false;
    }
    const [m, n] = [grid.length, grid[0].length];
    let pre = 0;
    for (let i = 0; i < m; ++i) {
        pre += grid[i].reduce((a, b) => a + b, 0);
        if (pre * 2 === s && i + 1 < m) {
            return true;
        }
    }
    pre = 0;
    for (let j = 0; j < n; ++j) {
        for (let i = 0; i < m; ++i) {
            pre += grid[i][j];
        }
        if (pre * 2 === s && j + 1 < n) {
            return true;
        }
    }
    return false;
}

3546. Equal Sum Grid Partition I

Description

Solutions

Solution 1: Enumeration + Prefix Sum

Comments