{x}
blog image

Maximum Rows Covered by Columns

You are given an m x n binary matrix matrix and an integer numSelect.

Your goal is to select exactly numSelect distinct columns from matrix such that you cover as many rows as possible.

A row is considered covered if all the 1's in that row are also part of a column that you have selected. If a row does not have any 1s, it is also considered covered.

More formally, let us consider selected = {c1, c2, ...., cnumSelect} as the set of columns selected by you. A row i is covered by selected if:

  • For each cell where matrix[i][j] == 1, the column j is in selected.
  • Or, no cell in row i has a value of 1.

Return the maximum number of rows that can be covered by a set of numSelect columns.

 

Example 1:

Input: matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2

Output: 3

Explanation:

One possible way to cover 3 rows is shown in the diagram above.
We choose s = {0, 2}.
- Row 0 is covered because it has no occurrences of 1.
- Row 1 is covered because the columns with value 1, i.e. 0 and 2 are present in s.
- Row 2 is not covered because matrix[2][1] == 1 but 1 is not present in s.
- Row 3 is covered because matrix[2][2] == 1 and 2 is present in s.
Thus, we can cover three rows.
Note that s = {1, 2} will also cover 3 rows, but it can be shown that no more than three rows can be covered.

Example 2:

Input: matrix = [[1],[0]], numSelect = 1

Output: 2

Explanation:

Selecting the only column will result in both rows being covered since the entire matrix is selected.

 

Constraints:

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

Solution Explanation: Maximum Rows Covered by Columns

This problem asks to find the maximum number of rows in a binary matrix that can be covered by selecting exactly numSelect columns. A row is considered covered if all its '1's are in the selected columns, or if the row contains only '0's.

Approach: Bit Manipulation and Enumeration

The most efficient approach leverages bit manipulation to represent rows and column selections concisely.

  1. Row Representation: Each row is converted into a binary number. Each bit in this number corresponds to a column; a '1' bit indicates a '1' in that column for the given row, and a '0' bit indicates a '0'. This allows us to efficiently check if a row is covered by a set of columns using bitwise operations.

  2. Column Selection Enumeration: We iterate through all possible combinations of selecting numSelect columns. This is done by iterating through numbers from 0 to 2n - 1 (where n is the number of columns), treating each number as a bitmask representing a column selection. We only consider bitmasks with exactly numSelect bits set (representing the selection of numSelect columns).

  3. Coverage Check: For each column selection (bitmask), we check how many rows are covered. A row is covered if its corresponding binary number is a subset of the column selection bitmask (i.e., the bitwise AND of the row's number and the column selection mask equals the row's number).

  4. Maximum Covered Rows: We keep track of the maximum number of covered rows found across all column selections. This maximum is the solution.

Time and Space Complexity Analysis

  • Time Complexity: O(2n * m), where 'n' is the number of columns and 'm' is the number of rows. The dominant factor is the iteration through all possible column selections (2n combinations), and for each selection, we check the coverage of 'm' rows. While we use bit manipulation for efficient checking, the exponential nature of the enumeration remains.

  • Space Complexity: O(m). The space used is primarily for storing the binary representation of each row (the rows array). The space for other variables is relatively constant.

Code Implementation (Python)

from functools import reduce
from operator import or_
 
class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        rows = []
        for row in matrix:
            mask = reduce(or_, (1 << j for j, x in enumerate(row) if x), 0) #Efficiently creates the row's binary representation
            rows.append(mask)
 
        ans = 0
        for mask in range(1 << len(matrix[0])): #Iterate through column selection bitmasks
            if bin(mask).count('1') != numSelect: #Check if exactly numSelect columns are selected
                continue
            t = sum((x & mask) == x for x in rows) #Count covered rows using bitwise AND
            ans = max(ans, t)
        return ans

The code in other languages (Java, C++, Go, TypeScript) follows a similar structure, adapting the syntax and bit manipulation functions accordingly. The core algorithm remains the same. Note that the Python code uses reduce and a generator expression for a concise way to create the row's binary representation. Other languages might require a more explicit loop for this step.