#3546

Medium

LeetCode Problem Workspace

Equal Sum Grid Partition I

Determine if an m x n matrix grid can be split into two non-empty sections with equal sums by making a single horizontal or vertical cut.

array matrix enumeration prefix sum

Problem Statement

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 the two resulting sections have equal sums.

Return true if such a partition exists; otherwise return false. A horizontal cut divides the grid between rows, while a vertical cut divides the grid between columns. Consider different partition strategies to find an optimal solution.

Examples

Example 1

Input: grid = [[1,4],[2,3]]

Output: true

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

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

Solution Approach

Prefix Sum for Efficient Calculation

To efficiently calculate the sum of sections after a potential cut, a prefix sum array can be used. This allows quick retrieval of sums for any section of the grid, reducing unnecessary recalculations.

Enumeration of Cuts

The problem boils down to checking if there exists a valid horizontal or vertical cut. For this, iterate over potential cut points (either row or column) and check if the sums on both sides of the cut are equal.

Optimization with Early Termination

Instead of checking all possible cuts blindly, leverage the prefix sum and check from the edges of the matrix toward the middle. This can help reduce unnecessary checks and improve performance for large grids.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. A brute force approach may result in O(m * n) time, while optimized solutions with prefix sums can potentially reduce this to O(m + n). Space complexity is O(m + n) for storing prefix sums and additional arrays for sum calculations.

What Interviewers Usually Probe

Can the candidate explain how to optimize the sum calculation for large grids?
Does the candidate use the array plus matrix pattern effectively?
Can the candidate propose an optimal cut enumeration strategy without brute force?

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for both horizontal and vertical cuts.
Overlooking the impact of large grids on performance.
Failing to optimize sum calculations and checking cuts in an inefficient manner.

Follow-up variants

What if the grid contains negative integers?
How would the solution change if multiple cuts were allowed?
Can you solve the problem for non-square grids?

FAQ

What is the approach to solving the Equal Sum Grid Partition I problem?

The key is to use prefix sums for efficient section sum calculation and then enumerate possible horizontal and vertical cuts to check for equal sums.

How can prefix sums help in the solution?

Prefix sums allow you to calculate the sum of any section of the grid in constant time, which is critical for checking cuts efficiently.

What are the time and space complexities of this problem?

The time complexity can range from O(m * n) in brute force solutions to O(m + n) with prefix sums. Space complexity is O(m + n) due to the storage of prefix sums.

What patterns are important for solving this problem?

The problem involves the 'array plus matrix' pattern and requires enumeration techniques to check for possible partition cuts.

Can GhostInterview help with optimizing my solution?

Yes, GhostInterview helps by offering guidance on efficient algorithms and demonstrating best practices for optimizing matrix partitioning problems.

terminal

Solution

Solution 1: Enumeration + Prefix Sum

First, we calculate the sum of all elements in the matrix, denoted as $s$. If $s$ is odd, it is impossible to divide the matrix into two parts with equal sums, so we directly return `false`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        s = sum(sum(row) for row in grid)
        if s % 2:
            return False
        pre = 0
        for i, row in enumerate(grid):
            pre += sum(row)
            if pre * 2 == s and i != len(grid) - 1:
                return True
        pre = 0
        for j, col in enumerate(zip(*grid)):
            pre += sum(col)
            if pre * 2 == s and j != len(grid[0]) - 1:
                return True
        return False

Continue Practicing

#3548 equal sum grid partition ii #3480 maximize subarrays after removing one conflicting pair #3434 maximum frequency after subarray operation