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.
The brute force approach involves generating all possible combinations of choosing numSelect columns from the n columns. For each combination, check how many rows can be covered and keep track of the maximum number of rows covered.
Since n is at most 12, the number of combinations is reasonable to compute exhaustively (up to 924 combinations in the worst case). This approach involves iterating through each row for each combination and checking if the selected columns cover the row or not.
The C implementation uses a bitmask to generate all possible combinations of column selections. The __builtin_popcount function is used to count the number of bits set, which corresponds to the number of columns selected in combination i. For each valid combination, the number of covered rows is calculated and compared to find the maximum.
Time Complexity: O(2^n * m * n), where n is the number of columns and m is the number of rows. The space complexity is O(1) as we only use a fixed amount of additional space.
This approach uses backtracking to optimize the selection of columns while maximizing the number of covered rows. Rather than generating all combinations upfront, we build the combinations dynamically and prune as we go, leveraging an early exit if further combinations can't yield better results.
The C implementation uses a recursive backtracking function. It dynamically builds up combinations of columns while keeping track of covered rows. Pruning occurs naturally by avoiding unnecessary deeper exploration once the number of columns selected is reached.
Time Complexity: O(C(n, numSelect) * m * n), where C(n, numSelect) is the binomial coefficient. Space complexity is O(n) due to recursive call stacks.
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.
Next, we enumerate all 2^n column selection schemes, where n is the number of columns in the matrix. For each column selection scheme, we check whether numSelect columns have been selected. If not, we skip it. Otherwise, we count how many rows in the matrix are covered by the selected columns, i.e., how many binary numbers rows[i] are equal to the bitwise AND of rows[i] and the column selection scheme mask. We then update the maximum number of rows.
The time complexity is O(2^n times m), and the space complexity is O(m). Where m and n are the number of rows and columns in the matrix, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force with Combinations | Time Complexity: O(2^n * m * n), where n is the number of columns and m is the number of rows. The space complexity is O(1) as we only use a fixed amount of additional space. |
| Optimized Backtracking | Time Complexity: O(C(n, numSelect) * m * n), where C(n, numSelect) is the binomial coefficient. Space complexity is O(n) due to recursive call stacks. |
| Binary Enumeration | — |
| 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. |
Leetcode 2397. Maximum Rows Covered by Columns | Biweekly Contest 86. • Code with Alisha • 2,409 views views
Watch 7 more video solutions →Practice Maximum Rows Covered by Columns with our built-in code editor and test cases.
Practice on FleetCode