Scale Engineer

Equal Sum Grid Partition I

Med
#3157Time: O(m*n * (m+n)). For each of the `m-1` horizontal cuts, we iterate through `m*n` elements. For each of the `n-1` vertical cuts, we also iterate through `m*n` elements, leading to a high time complexity.Space: O(1). We only use a few variables to store the sums, not counting the input grid.
Patterns
EnumerationPrefix Sum
Data structures
ArrayMatrix

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through every possible horizontal and vertical cut. For each potential cut, it calculates the sum of the elements in the two resulting partitions from scratch and checks if they are equal.

Algorithm

  • Iterate through each possible horizontal cut position r from 0 to m-2.
  • For each r, calculate sum1 (sum of elements in rows 0 to r) and sum2 (sum of elements in rows r+1 to m-1) by iterating through all cells of the grid.
  • If sum1 equals sum2, a valid partition is found, so return true.
  • If no horizontal cut works, iterate through each possible vertical cut position c from 0 to n-2.
  • For each c, calculate sum1 (sum of elements in columns 0 to c) and sum2 (sum of elements in columns c+1 to n-1) by iterating through all cells.
  • If sum1 equals sum2, return true.
  • If no cut is found after checking all possibilities, return false.

Walkthrough

The algorithm first considers all m-1 possible horizontal cuts. A horizontal cut can be made between row i and row i+1 for i from 0 to m-2. For each such cut, we calculate sum_top, the sum of all elements from row 0 to i, and sum_bottom, the sum of all elements from row i+1 to m-1. This requires iterating through all m*n cells for each potential cut. If sum_top equals sum_bottom, a valid partition is found, and we return true. If no valid horizontal cut is found, the algorithm proceeds to check all n-1 possible vertical cuts. A vertical cut can be made between column j and j+1 for j from 0 to n-2. Similarly, for each vertical cut, we calculate sum_left and sum_right. If they are equal, we return true. If all possible cuts are checked and none result in an equal sum partition, the function returns false.

class Solution {    public boolean equalSumGridPartition(int[][] grid) {        int m = grid.length;        int n = grid[0].length;         // Check horizontal cuts        for (int i = 0; i < m - 1; i++) {            long topSum = 0;            for (int r = 0; r <= i; r++) {                for (int c = 0; c < n; c++) {                    topSum += grid[r][c];                }            }             long bottomSum = 0;            for (int r = i + 1; r < m; r++) {                for (int c = 0; c < n; c++) {                    bottomSum += grid[r][c];                }            }             if (topSum == bottomSum) {                return true;            }        }         // Check vertical cuts        for (int j = 0; j < n - 1; j++) {            long leftSum = 0;            for (int c = 0; c <= j; c++) {                for (int r = 0; r < m; r++) {                    leftSum += grid[r][c];                }            }             long rightSum = 0;            for (int c = j + 1; c < n; c++) {                for (int r = 0; r < m; r++) {                    rightSum += grid[r][c];                }            }             if (leftSum == rightSum) {                return true;            }        }         return false;    }}

Complexity

Time

O(m*n * (m+n)). For each of the `m-1` horizontal cuts, we iterate through `m*n` elements. For each of the `n-1` vertical cuts, we also iterate through `m*n` elements, leading to a high time complexity.

Space

O(1). We only use a few variables to store the sums, not counting the input grid.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space.

Cons

  • Highly inefficient due to repeated calculations.

  • Likely to result in a 'Time Limit Exceeded' error for larger grids.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem