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.
| 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. |
| 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