#3548

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Equal Sum Grid Partition II

Determine if a matrix can be partitioned into two sections with an equal sum using a single cut.

array hash table 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's possible to make either one horizontal or one vertical cut on the grid such that the sum of the values in the resulting sections are equal.

The cut must divide the grid into two connected sections where every cell in a section is reachable from any other cell in that section. If such a partition exists, return true; otherwise, return false.

Examples

Example 1

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

Output: true

Example 2

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

Output: true

Example 3

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

Output: 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 Calculation

Calculate the prefix sum of the entire grid to quickly compute the sum of any subgrid. This step ensures that you can efficiently check possible cuts by comparing the sums of sections that would result from both vertical and horizontal cuts.

Array Scanning with Hash Lookup

Use array scanning along with hash lookups to identify potential cuts. You can iterate over the grid rows or columns and check if any possible partition results in equal sums using the precomputed prefix sum values.

Connected Component Validation

Once potential cuts are found, ensure that the resulting sections are connected. Check for disconnected components within any of the sections, which would invalidate the partition.

Complexity Analysis

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

The time complexity depends on how the prefix sum is computed and how efficiently you can check possible cuts using array scanning and hash lookups. The space complexity is determined by the storage required for the prefix sum and the hash maps used during the scanning process.

What Interviewers Usually Probe

Tests ability to manage large grids and perform efficient lookups.
Evaluates understanding of array manipulation, hash tables, and matrix partitioning.
Checks for efficient computation of subgrid sums and partition validation.

Common Pitfalls or Variants

Common pitfalls

Failing to handle large grids efficiently, leading to time limit exceeded errors.
Incorrectly assuming that a section is always connected after a cut, without checking for disconnection.
Not properly calculating prefix sums for quick access to subgrid sums, leading to unnecessary recomputation.

Follow-up variants

What if you are only allowed to make a horizontal cut?
Can the solution be optimized further for even larger grids?
How would the solution change if the grid contained negative numbers?

FAQ

What is the key technique for solving the Equal Sum Grid Partition II problem?

The problem is best approached using array scanning combined with hash lookups, particularly leveraging prefix sums to calculate subgrid sums efficiently.

How do I handle large grid sizes in this problem?

You should optimize your solution using prefix sums and hash maps to avoid recalculating sums repeatedly, which could lead to time limit exceeded errors.

What happens if a section becomes disconnected after a cut?

A disconnected section invalidates the partition, so you must ensure that the resulting sections after the cut remain connected.

Can I use dynamic programming to solve this problem?

Dynamic programming isn't necessary for this problem. Using prefix sums and hash lookups provides a more efficient solution with less overhead.

How can GhostInterview assist with tackling this problem?

GhostInterview offers hints on array scanning and hash lookup methods and provides guidance on handling grid partitions and common pitfalls effectively.

terminal

Solution

Method 1: Enumerate Partition Lines

We can first enumerate horizontal partition lines, compute the element sum of each resulting part, and use hash maps to record the occurrence count of elements in each part.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        def check(g: List[List[int]]) -> bool:
            m, n = len(g), len(g[0])
            s1 = s2 = 0
            cnt1 = defaultdict(int)
            cnt2 = defaultdict(int)
            for i, row in enumerate(g):
                for j, x in enumerate(row):
                    s2 += x
                    cnt2[x] += 1
            for i, row in enumerate(g[: m - 1]):
                for x in row:
                    s1 += x
                    s2 -= x
                    cnt1[x] += 1
                    cnt2[x] -= 1
                if s1 == s2:
                    return True
                if s1 < s2:
                    diff = s2 - s1
                    if cnt2[diff]:
                        if (
                            (m - i - 1 > 1 and n > 1)
                            or (
                                i == m - 2
                                and (g[i + 1][0] == diff or g[i + 1][-1] == diff)
                            )
                            or (n == 1 and (g[i + 1][0] == diff or g[-1][0] == diff))
                        ):
                            return True
                else:
                    diff = s1 - s2
                    if cnt1[diff]:
                        if (
                            (i + 1 > 1 and n > 1)
                            or (i == 0 and (g[0][0] == diff or g[0][-1] == diff))
                            or (n == 1 and (g[0][0] == diff or g[i][0] == diff))
                        ):
                            return True
            return False

        return check(grid) or check(list(zip(*grid)))

Continue Practicing

#3546 equal sum grid partition i #3434 maximum frequency after subarray operation #3044 most frequent prime