Maximum Rows Covered by Columns
MedPrompt
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:
- For each cell where
matrix[i][j] == 1, the columnjis inselected. - Or, no cell in row
ihas a value of1.
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 either0or1.1 <= numSelect <= n
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem into a search algorithm. It uses recursion with backtracking to generate every possible combination of numSelect columns. For each generated combination, it performs a full scan of the matrix to count how many rows are covered. The maximum count found across all combinations is the final answer.
Algorithm
- Define a recursive helper function, say
generateCombinations(start_col, count, selected_cols). - Base Case: When
countequalsnumSelect, a valid combinationselected_colshas been formed. - For this combination, iterate through each row of the matrix.
- To check if a row is covered, verify that for every cell
matrix[i][j] == 1, the columnjis present in theselected_colsset. - Count the number of covered rows for this combination and update a global maximum variable.
- Recursive Step: Iterate from
start_colton-1. For each columni:- Add column
ito the current selection. - Make a recursive call:
generateCombinations(i + 1, count + 1, selected_cols). - Backtrack: Remove column
ifrom the selection to explore other combinations.
- Add column
- The initial call to start the process is
generateCombinations(0, 0, new HashSet<>()).
Walkthrough
The main idea is to build a set of selected columns recursively. When the set reaches the desired size (numSelect), we evaluate it by checking every cell of the matrix. This is the most straightforward way to think about the problem but also the least performant.
class Solution { int maxRows = 0; int m, n; int[][] matrix; public int maximumRows(int[][] matrix, int numSelect) { this.m = matrix.length; this.n = matrix[0].length; this.matrix = matrix; generateCombinations(0, 0, new java.util.HashSet<>()); return maxRows; } private void generateCombinations(int startCol, int count, java.util.Set<Integer> selectedCols) { if (count == numSelect) { int currentCoveredRows = 0; for (int i = 0; i < m; i++) { boolean rowCovered = true; for (int j = 0; j < n; j++) { if (matrix[i][j] == 1 && !selectedCols.contains(j)) { rowCovered = false; break; } } if (rowCovered) { currentCoveredRows++; } } maxRows = Math.max(maxRows, currentCoveredRows); return; } for (int i = startCol; i < n; i++) { selectedCols.add(i); generateCombinations(i + 1, count + 1, selectedCols); selectedCols.remove(i); // Backtrack } }}Complexity
Time
O(C(n, numSelect) * m * n). The algorithm generates C(n, numSelect) combinations of columns. For each combination, it iterates through the entire `m x n` matrix to count covered rows. This is the slowest approach.
Space
O(numSelect). The space is used by the recursion stack, which goes up to a depth of `numSelect`, and the `HashSet` which stores up to `numSelect` column indices.
Trade-offs
Pros
Conceptually simple and directly models the problem of choosing combinations.
Easy to implement without requiring advanced data structures or techniques.
Cons
Highly inefficient due to the expensive O(m * n) check being performed for every single combination.
The time complexity makes it too slow for larger constraints, although it passes for the given small constraints.
This approach leverages the small constraint on n (number of columns <= 12) by using bitmasks. A subset of columns can be represented by an integer, where the j-th bit is 1 if column j is selected. The algorithm iterates through all 2^n possible column subsets. For each subset that has exactly numSelect columns (checked by counting set bits), it calculates the number of covered rows and updates the maximum.
Algorithm
- Preprocessing: Create an array
rowMasksof sizem. For each rowi,rowMasks[i]is an integer where thej-th bit is set to 1 ifmatrix[i][j] == 1. This takes O(m * n) time. - Initialize
maxCovered = 0. - Iterate through all possible column masks from
0to2^n - 1. Let the current mask becolMask. - Check if
colMaskrepresents a selection of exactlynumSelectcolumns by checking ifInteger.bitCount(colMask) == numSelect. - If it is a valid selection, calculate the number of covered rows.
- Initialize
currentCovered = 0. Iterate through each rowifrom0tom-1. - A row
iis covered if all its required columns (represented byrowMasks[i]) are included in the selected columns (colMask). This is checked efficiently with a bitwise AND:(rowMasks[i] & colMask) == rowMasks[i]. - If the condition is true, increment
currentCovered. - After checking all rows, update the global maximum:
maxCovered = Math.max(maxCovered, currentCovered). - Return
maxCovered.
Walkthrough
The key improvement over the first approach is optimizing the row-checking process. We first pre-process the matrix to represent each row's requirements as a bitmask. This allows checking if a row is covered in a single O(1) bitwise operation, which is much faster than iterating through the row's columns.
class Solution { public int maximumRows(int[][] matrix, int numSelect) { int m = matrix.length; int n = matrix[0].length; // Step 1: Pre-process matrix into row masks int[] rowMasks = new int[m]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { rowMasks[i] |= (1 << j); } } } int maxCovered = 0; // Step 2: Iterate through all 2^n possible column selections (masks) for (int colMask = 0; colMask < (1 << n); colMask++) { // Step 3: Check if the mask has exactly numSelect columns if (Integer.bitCount(colMask) == numSelect) { int currentCovered = 0; // Step 4: Check how many rows are covered by this mask for (int rowMask : rowMasks) { if ((rowMask & colMask) == rowMask) { currentCovered++; } } maxCovered = Math.max(maxCovered, currentCovered); } } return maxCovered; }}Complexity
Time
O(m * n + 2^n * m). The `m*n` is for preprocessing. The main loop runs `2^n` times, and inside it, we perform `m` checks. While `2^n` is larger than `C(n, numSelect)`, this approach is often faster than the first one because the work inside the loop is much smaller (O(m) vs O(m*n)).
Space
O(m). Space is required to store the `rowMasks` array.
Trade-offs
Pros
Efficiently checks for covered rows using O(1) bitwise operations.
Avoids recursion overhead.
Faster than the naive backtracking approach because the
O(n)factor in the inner loop is eliminated.
Cons
It checks all
2^nsubsets, even though we only care about subsets of sizenumSelect. This is less efficient than generating only the required combinations, especially whennumSelectis much smaller thann.
This is the most optimal solution, combining the best aspects of the previous two approaches. It uses a backtracking algorithm to intelligently generate only the necessary combinations of numSelect columns, thus avoiding the 2^n search space. Simultaneously, it uses bitmasks to represent both the column selections and row requirements, enabling a highly efficient O(1) check for whether a row is covered.
Algorithm
- Preprocessing: Same as the previous approach, create the
rowMasksarray in O(m * n) time. - Create a recursive function
generate(start_col, k, current_mask), wherekis the number of columns left to choose. - Base Case: If
kis 0, we have a valid combination incurrent_mask.- Count covered rows by iterating through
rowMasksand checking if(rowMask & current_mask) == rowMask. This takes O(m) time. - Update the global maximum.
- Count covered rows by iterating through
- Recursive Step: For each column
ifromstart_colton-1:- Recurse, selecting column
i:generate(i + 1, k - 1, current_mask | (1 << i)).
- Recurse, selecting column
Walkthrough
We generate combinations using recursion, but instead of passing a Set of columns, we build up a bitmask representing the selection. This allows us to use the efficient row-checking method from the second approach while only visiting the C(n, numSelect) combinations that are relevant, giving us the best of both worlds.
class Solution { int maxRows = 0; int m, n; int[] rowMasks; public int maximumRows(int[][] matrix, int numSelect) { this.m = matrix.length; this.n = matrix[0].length; // Step 1: Pre-process matrix into row masks this.rowMasks = new int[m]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { rowMasks[i] |= (1 << j); } } } generateCombinations(0, numSelect, 0); return maxRows; } private void generateCombinations(int startCol, int k, int currentMask) { // Base case: a combination of k columns is formed if (k == 0) { int currentCoveredRows = 0; for (int rowMask : rowMasks) { if ((rowMask & currentMask) == rowMask) { currentCoveredRows++; } } maxRows = Math.max(maxRows, currentCoveredRows); return; } // Pruning: if remaining columns are not enough to select k if (n - startCol < k) { return; } // Recursive step: iterate through possible next columns for (int i = startCol; i < n; i++) { // Select column i and recurse generateCombinations(i + 1, k - 1, currentMask | (1 << i)); } }}Complexity
Time
O(m * n + C(n, numSelect) * m). O(m * n) for preprocessing. The recursion generates C(n, numSelect) valid masks, and for each, we do O(m) work. This is guaranteed to be faster than or equal to the other approaches.
Space
O(m + n). O(m) for `rowMasks` and O(n) (or more precisely, O(numSelect)) for the recursion stack depth.
Trade-offs
Pros
Most efficient solution with the best time complexity.
Combines the targeted search of backtracking with the fast checking of bitmasking.
Avoids iterating through unnecessary combinations.
Cons
Slightly more complex to conceptualize and implement, as it requires understanding both backtracking and bit manipulation.
Solutions
Solution
class Solution {public int maximumRows(int[][] matrix, int numSelect) { int m = matrix.length, n = matrix[0].length; int[] rows = new int[m]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == 1) { rows[i] |= 1 << j; } } } int ans = 0; for (int mask = 1; mask < 1 << n; ++mask) { if (Integer.bitCount(mask) != numSelect) { continue; } int t = 0; for (int x : rows) { if ((x & mask) == x) { ++t; } } ans = Math.max(ans, t); } return ans; }}class Solution {public: int maximumRows(vector<vector<int>> &matrix, int numSelect) { int m = matrix.size(), n = matrix[0].size(); int rows[m]; memset(rows, 0, sizeof(rows)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j]) { rows[i] |= 1 << j; } } } int ans = 0; for (int mask = 1; mask < 1 << n; ++mask) { if (__builtin_popcount(mask) != numSelect) { continue; } int t = 0; for (int x : rows) { t += (x & mask) == x; } ans = max(ans, t); } return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.