What is the main approach for solving the 'Find a Good Subset of the Matrix' problem?

The main approach combines array scanning with hash lookup to evaluate valid subsets of rows in the matrix, ensuring each column sum is at most half the subset's size.

How do bit manipulation and hash tables help in solving this problem?

Bit manipulation allows efficient representation of subsets, while hash tables optimize the checking of column sums, reducing redundant calculations and speeding up the process.

What are common mistakes when solving the 'Find a Good Subset of the Matrix' problem?

Common mistakes include not optimizing the subset generation process, failing to handle edge cases, and missing the benefits of bit manipulation and hash lookups.

What should I focus on to solve this problem efficiently?

Focus on reducing the complexity of subset generation and sum checking, using techniques like bit manipulation and hash tables to speed up evaluations.

How does GhostInterview help with this problem?

GhostInterview provides hints, structured solutions, and targeted guidance to help optimize subset generation and effectively use bit manipulation and hash lookup.

#2732

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找到矩阵中的好子集

给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。从原矩阵中选出若干行构成一个行的非空子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是好子集。更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。…

数组哈希表位运算矩阵

题目描述

给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。

从原矩阵中选出若干行构成一个行的非空子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 好子集。

更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。

请你返回一个整数数组，它包含好子集的行下标，请你将其升序返回。

如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。

一个矩阵 grid 的行子集，是删除 grid 中某些（也可能不删除）行后，剩余行构成的元素集合。

示例 1：

输入：grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
输出：[0,1]
解释：我们可以选择第 0 和第 1 行构成一个好子集。
选出来的子集大小为 2 。
- 第 0 列的和为 0 + 0 = 0 ，小于等于子集大小的一半。
- 第 1 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 2 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 3 列的和为 0 + 1 = 1 ，小于等于子集大小的一半。

示例 2：

输入：grid = [[0]]
输出：[0]
解释：我们可以选择第 0 行构成一个好子集。
选出来的子集大小为 1 。
- 第 0 列的和为 0 ，小于等于子集大小的一半。

示例 3：

输入：grid = [[1,1,1],[1,1,1]]
输出：[]
解释：没有办法得到一个好子集。

提示：

m == grid.length
n == grid[i].length
1 <= m <= 10⁴
1 <= n <= 5
grid[i][j] 要么是 0 ，要么是 1 。

lightbulb

解题思路

方法一：分情况讨论

我们可以从小到大考虑答案选择的行数 $k$ 。

如果 $k = 1$ ，每一列的和最大为 $0$ ，那么必须满足有一行的所有元素都是 $0$ ，否则无法满足条件。
如果 $k = 2$ ，每一列的和最大为 $1$ ，那么必须存在有两行，且这两行的元素按位与之后的结果是 $0$ ，否则无法满足条件。
如果 $k = 3$ ，每一列的和最大也是 $1$ 。如果 $k = 2$ 不满足条件，那么 $k = 3$ 也一定不满足条件，所以我们不需要考虑所有 $k \gt 2$ 且 $k$ 为奇数的情况。
如果 $k = 4$ ，每一列的和最大为 $2$ ，此时一定是 $k = 2$ 不满足条件，也就是说，任意选取两行，都存在至少一个列的和为 $2$ 。我们在 $4$ 行中任意选取 $2$ 行，一共有 $C_4^2 = 6$ 种选法，那么存在至少 $6$ 个 $2$ 的列。由于列数 $n \le 5$ ，所以一定存在至少一列的和大于 $2$ ，所以 $k = 4$ 也不满足条件。
对于 $k \gt 4$ 且 $k$ 为偶数的情况，我们可以得出同样的结论，即 $k$ 一定不满足条件。

综上所述，我们只需要考虑 $k = 1$ 和 $k = 2$ 的情况即可。即判断是否有一行全为 $0$ ，或者是否存在两行按位与之后的结果为 $0$ 。

时间复杂度 $O(m \times n + 4^n)$ ，空间复杂度 $O(2^n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
        g = {}
        for i, row in enumerate(grid):
            mask = 0
            for j, x in enumerate(row):
                mask |= x << j
            if mask == 0:
                return [i]
            g[mask] = i
        for a, i in g.items():
            for b, j in g.items():
                if (a & b) == 0:
                    return sorted([i, j])
        return []

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Candidates should demonstrate knowledge of subset generation techniques, such as sliding windows or bit manipulation.
question_mark
Look for candidates who propose optimizing the checking of column sums using hash tables or other data structures.
question_mark
A good candidate will be able to reason about the trade-offs between time complexity and the constraints of the problem.

warning

常见陷阱

外企场景

error
Overlooking the need to optimize subset generation and column sum calculations can result in inefficient solutions.
error
Failing to handle edge cases, such as matrices with very small sizes or matrices where no valid subset exists.
error
Not leveraging bit manipulation for small column sizes may lead to unnecessary complexity in generating subsets.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider a variant where the matrix is not binary, but contains other values that must be summed and checked.
arrow_right_alt
A variant where the maximum size of the subset is restricted to a particular value could be used to challenge optimization skills.
arrow_right_alt
A dynamic variant where rows are added or removed from the matrix, requiring the solution to be updated incrementally.

help

常见问题

外企场景

继续练习

#3568 清理教室的最少移动 #2713 矩阵中严格递增的单元格数 #2711 对角线上不同值的数量差