3546. Equal Sum Grid Partition I

Problem Link

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

Solution

---

Python3

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        rows, cols = len(grid), len(grid[0])
        gridTotal = sum(x for row in grid for x in row)
 
        currTotal = sum(grid[0])
        total = gridTotal - currTotal
 
        for i in range(1, rows):
            if currTotal == total: 
                return True
 
            currentRowTotal = sum(grid[i])
            currTotal += currentRowTotal
            total -= currentRowTotal            
 
        def findColTotal(j):
            s = 0
            
            for index in range(rows):
                s += grid[index][j]
 
            return s
 
        currTotal = findColTotal(0)
        total = gridTotal - currTotal
 
        for j in range(1, cols):
            if currTotal == total: 
                return True
 
            currentColTotal = findColTotal(j)
            currTotal += currentColTotal
            total -= currentColTotal
 
        return False