Maximum Rows Covered by Columns — Problem & Solution
Maximum Rows Covered by Columns solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Rows Covered by Columns is a medium coding problem on arrays, matrix and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Bit Manipulation, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n binary matrix matrix and an integer numSelect. Select exactly numSelect distinct columns.
A row is covered when every column in which that row holds a 1 is among the selected columns. In particular, a row of all zeros is always covered.
Return the maximum number of rows that can be covered by a selection of numSelect columns.
Example 1
Input: matrix = [[0,1,0],[1,1,0],[0,0,0],[0,0,1]], numSelect = 2
Output: 3
Explanation: Selecting columns 0 and 1 covers rows 0, 1 and 2; row 3 needs column 2.
Example 2
Input: matrix = [[1,0],[0,1],[1,1]], numSelect = 1
Output: 1
Example 3
Input: matrix = [[1],[0]], numSelect = 1
Output: 2
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 12matrix[i][j] is either 0 or 11 <= numSelect <= n
Hints for Maximum Rows Covered by Columns
Hint 1
There are at most 2^12 = 4096 ways to choose columns — enumerate them.
Hint 2
Turn each row into a bitmask of its 1-columns, and each selection into a bitmask too.
Hint 3
A row with mask
ris covered by selectionsexactly whenr AND NOT s == 0. Try everyswithnumSelectbits set.
How to solve Maximum Rows Covered by Columns
With at most 12 columns, every selection fits in a 12-bit mask; enumerate the masks with exactly numSelect bits and test each row with one AND.
Approach
- Encode each row as
rows[i], the mask of columns where it holds a 1. - For every mask
sfrom 0 to 2^n - 1 whose popcount equalsnumSelect: - count the rows with
rows[i] AND NOT s == 0, and keep the maximum count.
Why it works
A row is covered exactly when none of its 1-columns lies outside the selection, which is the condition rows[i] AND NOT s == 0. Every legal selection is one of the masks examined, so the maximum is exact.
Complexity
- Time —
O(2^n · m) - Space —
O(m)
Pitfalls
- Exactly
numSelectcolumns must be chosen, not at most — though choosing more never uncovers a row, the masks must have the right popcount. - All-zero rows count as covered by any selection.
- Precompute row masks; re-scanning the matrix for every selection multiplies the work by
n.
Reference solution
Python
from typing import List
def maximumRows(matrix: List[List[int]], numSelect: int) -> int:
n = len(matrix[0])
rows = []
for row in matrix:
r = 0
for j in range(n):
if row[j]:
r |= 1 << j
rows.append(r)
best = 0
for s in range(1 << n):
if bin(s).count("1") != numSelect:
continue
cov = 0
for r in rows:
if r & ~s == 0:
cov += 1
if cov > best:
best = cov
return bestJava
public static 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 best = 0;
for (int s = 0; s < (1 << n); s++) {
if (Integer.bitCount(s) != numSelect) continue;
int cov = 0;
for (int r : rows) if ((r & ~s) == 0) cov++;
best = Math.max(best, cov);
}
return best;
}C++
int maximumRows(vector<vector<int>>& matrix, int numSelect) {
int m = matrix.size(), n = matrix[0].size();
vector<int> rows(m, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) if (matrix[i][j]) rows[i] |= 1 << j;
}
int best = 0;
for (int s = 0; s < (1 << n); s++) {
if (__builtin_popcount(s) != numSelect) continue;
int cov = 0;
for (int r : rows) if ((r & ~s) == 0) cov++;
best = max(best, cov);
}
return best;
}JavaScript
var maximumRows = function(matrix, numSelect) {
var m = matrix.length, n = matrix[0].length, rows = [];
for (var i = 0; i < m; i++) {
var r = 0;
for (var j = 0; j < n; j++) if (matrix[i][j]) r |= 1 << j;
rows.push(r);
}
var best = 0;
for (var s = 0; s < (1 << n); s++) {
var c = 0, x = s;
while (x) { c += x & 1; x >>= 1; }
if (c !== numSelect) continue;
var cov = 0;
for (var t = 0; t < m; t++) if ((rows[t] & ~s) === 0) cov++;
if (cov > best) best = cov;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal