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

Solution: Prefix Sum + Hash Table

• Time complexity: O(mn)
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {number[][]} grid
 * @return {boolean}
 */
const canPartitionGrid = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const valueMap = new Map();
  const rowSum = Array.from({ length: m }, () => 0);
  const colSum = Array.from({ length: n }, () => 0);
  let topSum = 0;
  let leftSum = 0;
  let totalSum = 0;

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const value = grid[row][col];

      totalSum += value;
      rowSum[row] += value;
      colSum[col] += value;

      if (valueMap.has(value)) {
        const range = valueMap.get(value);

        range.minRow = Math.min(row, range.minRow);
        range.maxRow = Math.max(row, range.maxRow);
        range.minCol = Math.min(col, range.minCol);
        range.maxCol = Math.max(col, range.maxCol);
      } else {
        valueMap.set(value, {
          minRow: row,
          maxRow: row,
          minCol: col,
          maxCol: col,
        });
      }
    }
  }

  const isConnected = (row1, col1, row2, col2, value) => {
    if (!valueMap.has(value)) return false;

    const { minRow, maxRow, minCol, maxCol } = valueMap.get(value);
    const rows = row2 - row1 + 1;
    const cols = col2 - col1 + 1;

    if (rows === 1 || cols === 1) {
      return grid[row1][col1] === value || grid[row2][col2] === value;
    }

    return minRow <= row2 && maxRow >= row1 && minCol <= col2 && maxCol >= col1;
  };

  for (let row = 0; row < m; row++) {
    topSum += rowSum[row];

    const bottomSum = totalSum - topSum;

    if (topSum === bottomSum) return true;

    if (isConnected(0, 0, row, n - 1, topSum - bottomSum)) return true;

    if (isConnected(row + 1, 0, m - 1, n - 1, bottomSum - topSum)) return true;
  }

  for (let col = 0; col < n; col++) {
    leftSum += colSum[col];

    const rightSum = totalSum - leftSum;

    if (leftSum === rightSum) return true;

    if (isConnected(0, 0, m - 1, col, leftSum - rightSum)) return true;

    if (isConnected(0, col + 1, m - 1, n - 1, rightSum - leftSum)) return true;
  }

  return false;
};