LeetCode 2397 - Maximum Rows Covered by Columns

Difficulty: 🟡 Medium
Topics: Array, Backtracking, Bit Manipulation, Matrix, Enumeration

Solution

Problem Understanding

This problem asks us to maximize the number of rows covered in a binary matrix after selecting exactly numSelect columns. Each row is covered if all 1s in that row are located in the selected columns, or if the row contains only 0s. The input is an m x n binary matrix, meaning each cell is either 0 or 1. The output is a single integer representing the maximum number of rows that can be covered using exactly numSelect columns.

The constraints are small, with both m and n being at most 12. This suggests that solutions with exponential time complexity are feasible, since 12 choose k is manageable for all valid k. Edge cases include rows that are all 0s (automatically covered), numSelect equal to n (all columns are selected), and rows that cannot be fully covered unless certain columns are selected. The problem guarantees valid inputs, so numSelect is at least 1 and at most n.

Approaches

The brute-force approach is to consider all possible combinations of numSelect columns. For each combination, we check every row to see if all its 1s are in the selected columns. This works because the input is small, but it is not efficient for larger matrices since the number of combinations is exponential, specifically C(n, numSelect).

The key insight to optimize is using bit manipulation. Each row can be represented as an integer bitmask, where 1 bits represent the positions of 1s in that row. Similarly, each set of selected columns can also be represented as a bitmask. To check whether a row is covered, we simply verify if (row_bitmask & selected_columns_bitmask) == row_bitmask. This avoids iterating over individual cells and allows us to enumerate column combinations efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(C(n, numSelect) * m * n)	O(m)	Iterate over all column combinations and all rows using nested loops
Optimal (Bitmask)	O(C(n, numSelect) * m)	O(m)	Convert rows to bitmask integers and check coverage using bitwise AND

Algorithm Walkthrough

Convert each row of the matrix into a bitmask. Each 1 in the row sets the corresponding bit in the integer.
Generate all possible combinations of numSelect columns using their indices.
For each combination, convert it into a bitmask by setting bits corresponding to the selected column indices.
Initialize a counter for covered rows. For each row bitmask, check if (row_bitmask & selected_columns_bitmask) == row_bitmask. If true, increment the counter.
Track the maximum covered rows across all combinations.
Return the maximum count.

Why it works: The algorithm guarantees that every possible column selection is evaluated, and using bitwise operations ensures that row coverage checks are accurate and efficient. The property (row_bitmask & selected_columns_bitmask) == row_bitmask precisely captures the coverage condition.

Python Solution

from itertools import combinations
from typing import List

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        row_masks = []
        
        for row in matrix:
            mask = 0
            for j, val in enumerate(row):
                if val:
                    mask |= (1 << j)
            row_masks.append(mask)
        
        max_covered = 0
        for cols in combinations(range(n), numSelect):
            col_mask = 0
            for c in cols:
                col_mask |= (1 << c)
            
            covered = sum(1 for row_mask in row_masks if (row_mask & col_mask) == row_mask)
            max_covered = max(max_covered, covered)
        
        return max_covered

The Python solution first converts each row to a bitmask to optimize coverage checks. It generates all column combinations of size numSelect, converts each combination to a bitmask, and counts the number of rows covered using bitwise operations. The maximum is returned.

Go Solution

package main

func maximumRows(matrix [][]int, numSelect int) int {
    m, n := len(matrix), len(matrix[0])
    rowMasks := make([]int, m)
    
    for i := 0; i < m; i++ {
        mask := 0
        for j := 0; j < n; j++ {
            if matrix[i][j] == 1 {
                mask |= 1 << j
            }
        }
        rowMasks[i] = mask
    }
    
    var maxCovered int
    var combine func(start, k, mask int)
    combine = func(start, k, mask int) {
        if k == 0 {
            covered := 0
            for _, rowMask := range rowMasks {
                if rowMask & mask == rowMask {
                    covered++
                }
            }
            if covered > maxCovered {
                maxCovered = covered
            }
            return
        }
        for i := start; i < n; i++ {
            combine(i+1, k-1, mask | (1 << i))
        }
    }
    
    combine(0, numSelect, 0)
    return maxCovered
}

The Go implementation uses a recursive combination generator instead of itertools.combinations. Each selected set of columns is converted to a bitmask and checked against all row masks, similar to Python. Go-specific considerations include using slices for row masks and integer bitwise operations.

Worked Examples

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

Convert rows to bitmask: [0b000, 0b101, 0b011, 0b001]
Generate all 2-column combinations: (0,1), (0,2), (1,2)
For combination (0,2) → col_mask = 0b101
Row coverage: 0b000 & 0b101 == 0b000 → covered, 0b101 & 0b101 == 0b101 → covered, 0b011 & 0b101 == 0b001 → not covered, 0b001 & 0b101 == 0b001 → covered
Covered rows = 3, which is the maximum

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

Row masks: [0b1, 0b0]
Only column 0 can be selected → mask 0b1
Coverage: 0b1 & 0b1 == 0b1 → covered, 0b0 & 0b1 == 0b0 → covered
Covered rows = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(C(n, numSelect) * m)	We generate all combinations of columns and check coverage for all rows
Space	O(m)	We store one bitmask per row

The complexity is feasible because n and m are at most 12, so even the largest combination count C(12, 6) is manageable.

Test Cases

# Provided examples
assert Solution().maximumRows([[0,0,0],[1,0,1],[0,1,1],[0,0,1]], 2) == 3  # covers 3 rows
assert Solution().maximumRows([[1],[0]], 1) == 2  # covers both rows

# Edge cases
assert Solution().maximumRows([[0,0],[0,0]], 1) == 2  # all zero rows
assert Solution().maximumRows([[1,1],[1,1]], 2) == 2  # all ones, need all columns
assert Solution().maximumRows([[1,0,0],[0,1,0],[0,0,1]], 1) == 1  # can cover only one row
assert Solution().maximumRows([[1,0,1],[1,1,0],[0,1,1]], 2) == 2  # overlapping coverage

Test	Why
Example 1	Basic scenario with mixed coverage
Example 2	Single column matrix
All zero rows	Should cover automatically regardless of selection
All ones rows	Requires all columns to cover
Sparse single selection	Only one row can be covered
Overlapping coverage	Tests optimal selection among overlapping ones

Edge Cases

The first edge case is a matrix with all zeros. Every row should be automatically covered regardless of column selection, which could trip up implementations that check only for 1s. Our solution handles it naturally using bitmasks, as the mask for a zero row is 0, which is always covered.

The second edge case is a matrix with all ones. This requires careful column selection; if numSelect < n, not all rows can be covered. The algorithm correctly evaluates all combinations and chooses the one maximizing coverage.

The third edge case is when numSelect equals n. In this situation, all columns are selected, and all rows with