Find a Good Subset of the Matrix — LeetCode 2732 Python Solution

The problem

You are given a 0-indexed m x n binary matrix grid. Let us call a non-empty subset of rows good if the sum of each column of the subset is at most half of the length of the subset.

Example

Input

grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]

Output

[0,1]

Explanation

We can choose the 0th and 1st rows to create a good subset of rows.

Python solution

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 []

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2732. Find a Good Subset of the Matrix is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems