How can I maximize the number of equal rows in a binary matrix?

To maximize equal rows, scan each row and use a hash table to track patterns. Flip columns to match the most frequent pattern.

What is the time complexity of the solution?

The time complexity is O(n * m), where n is the number of rows and m is the number of columns.

What is the key insight behind solving this problem?

The key insight is to use a hash table to track row patterns and flip columns to maximize the occurrence of the most frequent row pattern.

How does the XOR operation help in flipping columns?

The XOR operation helps by transforming rows in a way that mimics the effect of flipping specific columns. It ensures that rows are either all zeros or all ones after flipping columns.

What are the common pitfalls in this problem?

Common pitfalls include not properly considering the XOR operation's effects, overcomplicating the solution, or missing edge cases like matrices with no flips required.

#1072

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

按列翻转得到最大值等行数

给定 m x n 矩阵 matrix 。你可以从中选出任意数量的列并翻转其上的每个单元格。（即翻转后，单元格的值从 0 变成 1 ，或者从 1 变为 0 。）返回经过一些翻转后，行内所有值都相等的最大行数。示例 1：输入： matrix = [[0,1],[1,1]] 输出： 1 解…

数组哈希表矩阵

题目描述

给定 m x n 矩阵 matrix 。

你可以从中选出任意数量的列并翻转其上的每个单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）

返回 经过一些翻转后，行内所有值都相等的最大行数 。

示例 1：

输入：matrix = [[0,1],[1,1]]
输出：1
解释：不进行翻转，有 1 行所有值都相等。

示例 2：

输入：matrix = [[0,1],[1,0]]
输出：2
解释：翻转第一列的值之后，这两行都由相等的值组成。

示例 3：

输入：matrix = [[0,0,0],[0,0,1],[1,1,0]]
输出：2
解释：翻转前两列的值之后，后两行由相等的值组成。

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] == 0 或 1

lightbulb

解题思路

方法一：哈希表

我们观察发现，如果矩阵中的两行满足以下条件之一，则它们可以通过翻转某些列的方式得到相等的行：

两行的对应位置元素相等，即如果其中一行元素为 $1,0,0,1$ ，则另一行元素也为 $1,0,0,1$ ；
两行的对应位置元素相反，即如果其中一行元素为 $1,0,0,1$ ，则另一行元素为 $0,1,1,0$ 。

我们称满足以上条件之一的两行元素为“等价行”，那么题目所求的答案即为矩阵中最多包含等价行的行数。

因此，我们可以遍历矩阵的每一行，将每一行转换成第一个元素为 $0$ 的“等价行”。具体做法如下：

如果当前行的第一个元素为 $0$ ，那么当前行的元素保持不变；
如果当前行的第一个元素为 $1$ ，那么我们将当前行的每个元素进行翻转，即 $0$ 变成 $1$ , $1$ 变成 $0$ 。也就是说，我们将以 $1$ 开头的行翻转成以 $0$ 开头的“等价行”。

这样一来，我们只需要用一个哈希表来统计转换后的每一行的出现次数，其中键为转换后的行（可以将所有数字拼接成一个字符串），值为该行出现的次数。最后，哈希表中值的最大值即为矩阵中最多包含等价行的行数。

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

相似题目：

2128. 通过翻转行或列来去除所有的 1

1

2

3

4

5

6

7

8

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cnt = Counter()
        for row in matrix:
            t = tuple(row) if row[0] == 0 else tuple(x ^ 1 for x in row)
            cnt[t] += 1
        return max(cnt.values())

speed

复杂度分析

指标	值
时间	O(n \cdot m)
空间	O(n \cdot m)

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of binary operations and pattern matching within arrays.
question_mark
Gauge the candidate's ability to utilize hash tables effectively for optimizing solutions.
question_mark
Evaluate the candidate's approach to reducing unnecessary computations when flipping columns.

warning

常见陷阱

外企场景

error
Forgetting to account for the XOR operation's effect on the row patterns when flipping columns.
error
Overcomplicating the solution by trying to brute-force all possible column flips instead of using a hash table for optimization.
error
Missing edge cases such as matrices where no flips are needed or where flipping results in fewer equal rows.

swap_horiz

进阶变体

外企场景

arrow_right_alt
How would the solution change if we could only flip a single column?
arrow_right_alt
What if the matrix had more than two distinct values (e.g., 0, 1, and 2)?
arrow_right_alt
Can the solution be optimized further using advanced techniques like bitwise manipulation or dynamic programming?

help

常见问题

外企场景

继续练习

#1074 元素和为目标值的子矩阵数量 #959 由斜杠划分区域 #1275 找出井字棋的获胜者