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.

#3546

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

等和矩阵分割 I

给你一个由正整数组成的 m x n 矩阵 grid 。你的任务是判断是否可以通过一条水平或一条垂直分割线将矩阵分割成两部分，使得：分割后形成的每个部分都是非空的。两个部分中所有元素的和相等。如果存在这样的分割，返回 true ；否则，返回 false 。示例 1：输入： gri…

数组矩阵枚举前缀和

题目描述

给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：

分割后形成的每个部分都是非空的。
两个部分中所有元素的和相等。

如果存在这样的分割，返回 true；否则，返回 false。

示例 1：

输入： grid = [[1,4],[2,3]]

输出： true

解释：

在第 0 行和第 1 行之间进行水平分割，得到两个非空部分，每部分的元素之和为 5。因此，答案是 true。

示例 2：

输入： grid = [[1,3],[2,4]]

输出： false

解释：

无论是水平分割还是垂直分割，都无法使两个非空部分的元素之和相等。因此，答案是 false。

提示：

1 <= m == grid.length <= 10⁵
1 <= n == grid[i].length <= 10⁵
2 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

lightbulb

解题思路

方法一：枚举 + 前缀和

我们先计算矩阵中所有元素的和，记为 $s$ 。如果 $s$ 是奇数，则不可能将矩阵分割成两个和相等的部分，直接返回 false。

如果 $s$ 是偶数，我们可以枚举所有可能的分割线，判断是否存在一条分割线将矩阵分割成两个和相等的部分。

我们从上到下遍历每一行，计算当前行之前所有行的元素之和 $\textit{pre}$ ，如果 $\textit{pre} \times 2 = s$ ，且当前行不是最后一行，则说明可以在当前行和下一行之间进行水平分割，返回 true。

如果没有找到这样的分割线，我们再从左到右遍历每一列，计算当前列之前所有列的元素之和 $\textit{pre}$ ，如果 $\textit{pre} \times 2 = s$ ，且当前列不是最后一列，则说明可以在当前列和下一列之间进行垂直分割，返回 true。

如果没有找到这样的分割线，则返回 false。

时间复杂度 $O(m \times n)$ ，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$ ，只使用了常数级别的额外空间。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#3548 等和矩阵分割 II #3480 删除一个冲突对后最大子数组数目 #3434 子数组操作后的最大频率