1072. Flip Columns For Maximum Number of Equal Rows

Problem

You are given an m x n binary matrix matrix.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).

Return the maximum number of rows that have all values equal after some number of flips.

https://todo

Example 1:

Input: matrix = [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

Input: matrix = [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

Input: matrix = [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is either 0 or 1.

Test Cases

1
2

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13

import pytest

from solution import Solution


@pytest.mark.parametrize('matrix, expected', [
    ([[0,1],[1,1]], 1),
    ([[0,1],[1,0]], 2),
    ([[0,0,0],[0,0,1],[1,1,0]], 2),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, matrix, expected):
    assert sol.maxEqualRowsAfterFlips(matrix) == expected

Thoughts

如果某一行经过若干列的翻转可以变成全零（或全一），那么初始时跟它完全相同的行也会变成全零（或全一），而跟它完全相反（零一互补）的行会变成全一（或全零）。

把 matrix 中完全相同或互补的行归为一堆，最终看最大的一堆有多少行即可。

为了方便地处理互补的行，可以把所有行的第一个数字都翻转成一样的，比如都是 1。如果一行的第一个数字原本就是 1 则不用动，如果是 0 则把每个数字都翻转。

时间复杂度 O(m * n)，空间复杂度最坏情况也是 O(m * n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

from collections import defaultdict


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: list[list[int]]) -> int:
        counter: dict[tuple[int], int] = defaultdict(int)
        for row in matrix:
            if row[0]:
                key = tuple(row)
            else:
                key = tuple(1 - x for x in row)
            counter[key] += 1

        return max(counter.values())

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章