3548. Equal Sum Grid Partition II

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 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

Solution

---

Python3

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        rows, cols = len(grid), len(grid[0])
 
        MAXV = 100000
        prefixRowWise = [0] * rows
        prefixColWise = [0] * cols
 
        minRow = [None] * (MAXV + 1)
        maxRow = [None] * (MAXV + 1)
        minCol = [None] * (MAXV + 1)
        maxCol = [None] * (MAXV + 1)
 
        for i in range(rows):
            for j in range(cols):
                val = grid[i][j]
                prefixRowWise[i] += val
                prefixColWise[j] += val
 
                if minRow[val] is None:
                    minRow[val] = maxRow[val] = i
                    minCol[val] = maxCol[val] = j
                else:
                    minRow[val] = min(minRow[val], i)
                    maxRow[val] = max(maxRow[val], i)
                    minCol[val] = min(minCol[val], j)
                    maxCol[val] = max(maxCol[val], j)
 
        totalRowSum = sum(prefixRowWise)
        totalColSum = totalRowSum
 
        currentRowUpperSum = 0
        for i in range(rows - 1):
            currentRowUpperSum += prefixRowWise[i]
            lowerSegmentSum = totalRowSum - currentRowUpperSum
            if currentRowUpperSum == lowerSegmentSum:
                return True
            elif currentRowUpperSum > lowerSegmentSum:
                diff = currentRowUpperSum - lowerSegmentSum
                if diff <= MAXV and minRow[diff] is not None:
                    if i == 0 or cols == 1:
                        if diff in (grid[0][0], grid[0][cols - 1], grid[i][0]):
                            return True
                    elif minRow[diff] <= i:
                        return True
            else:
                diff = lowerSegmentSum - currentRowUpperSum
                if diff <= MAXV and maxRow[diff] is not None:
                    if i == rows - 2 or cols == 1:
                        if diff in (grid[i + 1][0], grid[i + 1][cols - 1], grid[rows - 1][0]):
                            return True
                    elif maxRow[diff] > i:
                        return True
 
        currentColLeftSum = 0
        for j in range(cols - 1):
            currentColLeftSum += prefixColWise[j]
            rightSegmentSum = totalColSum - currentColLeftSum
            if currentColLeftSum == rightSegmentSum:
                return True
            elif currentColLeftSum > rightSegmentSum:
                diff = currentColLeftSum - rightSegmentSum
                if diff <= MAXV and minCol[diff] is not None:
                    if j == 0 or rows == 1:
                        if diff in (grid[0][0], grid[rows - 1][0]):
                            return True
                    elif minCol[diff] <= j:
                        return True
            else:
                diff = rightSegmentSum - currentColLeftSum
                if diff <= MAXV and maxCol[diff] is not None:
                    if j == cols - 2 or rows == 1:
                        if diff in (grid[0][j + 1], grid[rows - 1][j + 1]):
                            return True
                    elif maxCol[diff] > j:
                        return True
 
        return False