Equal Sum Grid Partition I

medium prefix sum matrix enumeration

Problem

You are given an m × n matrix grid of positive integers. Decide if it is possible to make either one horizontal or one vertical cut so that both resulting sections are non-empty and have equal sums. Return true if such a partition exists, otherwise false.

Inputgrid = [[1,4],[2,3]]

Outputtrue

A horizontal cut between row 0 and row 1 gives two sections, each summing to 5, so the answer is true.

grid (rows separated by ;, values by ,)

def canPartitionGrid(grid):
    m, n = len(grid), len(grid[0])
    total = sum(v for row in grid for v in row)
    # horizontal cut: grow the top section row by row
    top = 0
    for r in range(m - 1):
        top += sum(grid[r])
        if 2 * top == total:        # top == bottom
            return True
    # vertical cut: grow the left section column by column
    left = 0
    for c in range(n - 1):
        for r in range(m):
            left += grid[r][c]
        if 2 * left == total:       # left == right
            return True
    return False

function canPartitionGrid(grid) {
  const m = grid.length, n = grid[0].length;
  let total = 0;
  for (const row of grid) for (const v of row) total += v;
  // horizontal cut: grow the top section row by row
  let top = 0;
  for (let r = 0; r < m - 1; r++) {
    for (let c = 0; c < n; c++) top += grid[r][c];
    if (2 * top === total) return true;   // top === bottom
  }
  // vertical cut: grow the left section column by column
  let left = 0;
  for (let c = 0; c < n - 1; c++) {
    for (let r = 0; r < m; r++) left += grid[r][c];
    if (2 * left === total) return true;  // left === right
  }
  return false;
}

boolean canPartitionGrid(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    long total = 0;
    for (int[] row : grid) for (int v : row) total += v;
    // horizontal cut: grow the top section row by row
    long top = 0;
    for (int r = 0; r < m - 1; r++) {
        for (int c = 0; c < n; c++) top += grid[r][c];
        if (2 * top == total) return true;   // top == bottom
    }
    // vertical cut: grow the left section column by column
    long left = 0;
    for (int c = 0; c < n - 1; c++) {
        for (int r = 0; r < m; r++) left += grid[r][c];
        if (2 * left == total) return true;  // left == right
    }
    return false;
}

bool canPartitionGrid(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    long long total = 0;
    for (auto& row : grid) for (int v : row) total += v;
    // horizontal cut: grow the top section row by row
    long long top = 0;
    for (int r = 0; r < m - 1; r++) {
        for (int c = 0; c < n; c++) top += grid[r][c];
        if (2 * top == total) return true;   // top == bottom
    }
    // vertical cut: grow the left section column by column
    long long left = 0;
    for (int c = 0; c < n - 1; c++) {
        for (int r = 0; r < m; r++) left += grid[r][c];
        if (2 * left == total) return true;  // left == right
    }
    return false;
}

Explanation

A single straight cut can only be horizontal (between two rows) or vertical (between two columns). After the cut, one section is the part above/left of the line and the other is the rest, so the two sums always add up to the whole grid total.

That gives a clean test: a balanced cut exists exactly when one section equals total / 2. Because every value is positive, we never have to re-add the same cells — we can sweep the cut line and keep a running prefix sum of the growing section.

For horizontal cuts we let top accumulate full rows from the top. After adding row r (for r from 0 to m-2, keeping both sides non-empty) we check 2 * top == total. If it holds, the bottom section equals the top, so we return true.

For vertical cuts we do the symmetric thing with left accumulating full columns. After adding column c (for c from 0 to n-2) we check 2 * left == total.

If neither sweep finds a balance, no valid cut exists and we return false. Example: grid = [[1,4],[2,3]] has total = 10; after row 0, top = 5 and 2 · 5 = 10, so a horizontal cut works.

Time: O(m · n) Space: O(1)