Scale Engineer

Equal Sum Grid Partition II

Hard
#3159Time: O(m*n * (m+n)). For each of the `m-1` horizontal cuts, we might iterate over `O(m*n)` cells in the worst case. A similar logic applies to the `n-1` vertical cuts, leading to a very high time complexity.Space: O(m + n) to store the pre-calculated row and column sums.
Patterns
EnumerationPrefix Sum
Data structures
ArrayHash TableMatrix

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible horizontal and vertical cut. For each potential cut, it calculates the sum of elements in the two resulting sections. If the sums are not equal, it naively scans one of the sections to find a cell that can be discounted to make the sums equal, while also checking the connectivity constraint.

Algorithm

  • First, pre-calculate the sum of each row and each column to speed up the sum calculation for sections. This takes O(m*n) time.
  • Iterate through all m-1 possible horizontal cuts.
  • For each horizontal cut, calculate the sum of the top section (sum1) and the bottom section (sum2).
  • Check the three conditions:
    1. If sum1 == sum2, a valid partition is found, return true.
    2. If sum1 > sum2, iterate through every cell in the top section. If a cell's value equals sum1 - sum2, check if removing it preserves connectivity. If so, a valid partition is found, return true.
    3. If sum2 > sum1, perform a similar check on the bottom section.
  • If no valid horizontal cut is found, repeat the entire process for all n-1 possible vertical cuts.
  • If no valid partition is found after checking all possible cuts, return false.

Walkthrough

The brute-force method involves a straightforward, exhaustive search. We begin by pre-calculating row and column sums to avoid re-calculating them for every partition, which is a minor optimization. Then, we loop through each possible horizontal cut line. For each cut, we find the sums of the two resulting partitions. If they aren't equal, we determine the difference, diff, and then iterate through every single cell of the larger partition to see if any cell's value matches diff. If a match is found, we perform a check to ensure that removing this cell doesn't violate the connectivity rule. The connectivity check is based on the dimensions of the partition: a multi-row, multi-column section always remains connected, but a single-row or single-column section only remains connected if an endpoint is removed. If no valid horizontal cut works, we apply the same logic to all possible vertical cuts. This method is simple but highly inefficient due to the repeated scanning of grid sections.

Complexity

Time

O(m*n * (m+n)). For each of the `m-1` horizontal cuts, we might iterate over `O(m*n)` cells in the worst case. A similar logic applies to the `n-1` vertical cuts, leading to a very high time complexity.

Space

O(m + n) to store the pre-calculated row and column sums.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Uses minimal extra space, mainly for storing row and column sums.

Cons

  • Extremely inefficient and will likely result in a 'Time Limit Exceeded' error for larger grids.

  • The nested loops lead to a high polynomial time complexity.

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