#2397

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Maximum Rows Covered by Columns

Select exactly numSelect columns from a binary matrix to maximize rows where all ones are covered efficiently using backtracking.

array backtracking bit manipulation matrix enumeration

Problem Statement

You are given an m x n binary matrix and an integer numSelect. Your task is to choose exactly numSelect distinct columns to maximize the number of rows that are covered.

A row is covered if every 1 in that row corresponds to a selected column. Rows with no ones are automatically covered. Determine the maximum count of covered rows that can be achieved with exactly numSelect columns.

Examples

Example 1

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

Output: 3

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

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 Approach

Backtracking with Pruning

Generate all combinations of numSelect columns recursively, and prune paths where remaining columns cannot exceed the current best coverage.

Bitmask Representation

Use bitmask integers to represent which columns are selected and which ones exist in each row. This allows O(1) checks for whether a row is covered.

Counting Covered Rows Efficiently

For each valid selection of columns, iterate through rows using bit operations to count how many are fully covered. Update the maximum accordingly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(C(n, numSelect) * m) due to generating combinations of columns and checking all rows. Space complexity is O(m) for storing bitmasks and recursion stack usage during backtracking.

What Interviewers Usually Probe

Checks if you understand recursive backtracking with pruning.
Tests efficient row coverage checks using bit manipulation.
Wants candidates to reason about combinatorial limits and avoid unnecessary computation.

Common Pitfalls or Variants

Common pitfalls

Not handling rows with all zeros correctly, which are automatically covered.
Inefficiently checking row coverage without bitmasking, causing timeouts.
Failing to prune column combinations that cannot improve the current maximum.

Follow-up variants

Maximize rows covered when selecting up to numSelect columns instead of exactly.
Find the minimum number of columns needed to cover all rows.
Optimize coverage when matrix dimensions are larger and require advanced pruning.

FAQ

What is the main pattern in Maximum Rows Covered by Columns?

The main pattern is backtracking search with pruning to explore combinations efficiently.

Can I use bit manipulation to speed up coverage checks?

Yes, representing selected columns and row ones as bitmasks allows O(1) coverage checks.

How do I handle rows with no ones?

Rows with no ones are considered covered automatically and do not require any columns.

Is a brute-force approach viable for larger matrices?

For matrices up to 12x12, brute-force with pruning works, but larger matrices need optimized pruning or heuristics.

How does GhostInterview assist with this problem?

GhostInterview tracks combinations, prunes impossible selections, and calculates row coverage efficiently using bit operations.

terminal

Solution

Solution 1: Binary Enumeration

First, we convert each row of the matrix into a binary number and record it in the array $rows$. Here, $rows[i]$ represents the binary number corresponding to the $i$-th row, and the $j$-th bit of this binary number $rows[i]$ represents the value of the $i$-th row and $j$-th column.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)
            rows.append(mask)

        ans = 0
        for mask in range(1 << len(matrix[0])):
            if mask.bit_count() != numSelect:
                continue
            t = sum((x & mask) == x for x in rows)
            ans = max(ans, t)
        return ans

Continue Practicing

#2212 maximum points in an archery competition #2151 maximum good people based on statements #2708 maximum strength of a group