Maximum Rows Covered by Columns

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from typing import List

class Solution:
    def next_popcount(self, n: int) -> int:
        c = (n & -n)
        r = n + c
        return (((r ^ n) >> 2) // c) | r

    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m = len(matrix)
        n = len(matrix[0])
        res = 0
        mask = (1 << numSelect) - 1

        while mask < (1 << n):
            rows = 0
            for i in range(m):
                for j in range(n):
                    if matrix[i][j] and (mask & (1 << j)) == 0:
                        break
                else: # This else is tied to the for-loop
                    rows += 1
            res = max(res, rows)
            mask = self.next_popcount(mask)

        return res