Watch 8 video solutions for Maximum Rows Covered by Columns, a medium level problem involving Array, Backtracking, Bit Manipulation. This walkthrough by Code with Alisha has 2,409 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
matrix[i][j] == 1, the column j is in selected.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.lengthn == matrix[i].length1 <= m, n <= 12matrix[i][j] is either 0 or 1.1 <= numSelect <= nProblem Overview: You are given a binary matrix where each row contains 0s and 1s. You must select exactly numSelect columns. A row is considered covered if every column containing a 1 in that row is included in your selected columns. The goal is to choose columns that maximize the number of covered rows.
Approach 1: Brute Force with Column Combinations (Time: O(C(n,k) * m * n), Space: O(1))
The direct approach enumerates every combination of numSelect columns from the total n columns. For each combination, iterate through all m rows and check whether the row is fully covered. A row is valid if every index containing 1 is present in the chosen column set. The check is implemented by scanning each column of the row or tracking selected columns with a boolean array or set. This approach is simple and easy to reason about because it explicitly evaluates every valid column subset. The downside is the combinational explosion when n grows, but the constraint is typically small enough that C(n, k) remains manageable.
Approach 2: Optimized Backtracking with Bit Manipulation (Time: O(C(n,k) * m), Space: O(n))
This approach improves row validation using bit manipulation. Convert each row into a bitmask where bit j represents whether column j contains a 1. During backtracking, build a column selection mask while choosing columns recursively. After selecting numSelect columns, iterate through all row masks and check if the row is covered using a bitwise condition: (rowMask & selectedMask) == rowMask. This operation verifies that every required column in the row is included in the chosen set. Bitwise checks run in constant time, which removes the inner column scan and significantly speeds up evaluation for each combination.
The backtracking structure systematically generates column subsets while pruning when the remaining columns cannot reach numSelect. Each recursion step either includes the current column or skips it, similar to subset generation. Because row validation is reduced to a single bitwise comparison, the runtime becomes dominated by the number of combinations rather than matrix traversal.
Recommended for interviews: Start by describing the combination enumeration idea because it clearly models the search space of column subsets. Then transition to the optimized bitmask version. Interviewers typically expect the bit manipulation + backtracking solution since it reduces row validation to O(1) checks and demonstrates strong understanding of subset enumeration and binary representations in matrices.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Column Combinations | O(C(n,k) * m * n) | O(1) | Good baseline solution. Useful when constraints are small and clarity is preferred over optimization. |
| Backtracking with Bitmask Optimization | O(C(n,k) * m) | O(n) | Preferred solution for interviews. Efficient row coverage checks using bitwise operations. |