Maximum Rows Covered by Columns solution and explanation
7 more videos on this problem
Leetcode 2397. Maximum Rows Covered by Columns | Biweekly Contest 86.Code with Alisha · 13:05 · 2K views
2397. Maximum Rows Covered by Columns | Biweekly Contest 86 | LeetCode 2397Bro Coders · 11:34 · 1K views
2397. Maximum Rows Covered by Columns (Leetcode Medium)Programming Live with Larry · 8:35 · 372 views
【每日一题】LeetCode 2397. Maximum Rows Covered by ColumnsHuifeng Guan · 13:54 · 327 views
✅ Leetcode Biweekly Contest 86 | Maximum Rows Covered by Columns | Leetcode Solutions C++ | CodingLeetcode Hindi · 4:38 · 254 views
Leetcode 2397: Maximum Rows Covered by ColumnsAlgorithms Casts · 13:34 · 241 views
6173. Maximum Rows Covered by Columns || Leetcode Contest Medium || CPPCoding Techniques with Komal | Newton School · 6:20 · 203 views
Leetcode 2397. Maximum Rows Covered by Columns - combination and check, sort of brute forceCode-Yao · 10:52 · 38 views
The problem
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
Approach overview
Problem 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 1: Brute Force with Combinations
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.
from itertools import combinations
def maxRowsCovered(matrix, numSelect):
m = len(matrix)
n = len(matrix[0])
maxCovered = 0
columns = range(n)
for cols in combinations(columns, numSelect):
covered = 0
for row in matrix:
if all(row[c] == 0 or c in cols for c in range(n)):
covered += 1
maxCovered = max(maxCovered, covered)
return maxCovered
matrix = [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 0, 1]]
numSelect = 2
print(maxRowsCovered(matrix, numSelect))import java.util.ArrayList;
import java.util.List;
public class MaxRowsCovered {
public static int maxRowsCovered(int[][] matrix, int numSelect) {
int m = matrix.length;
int n = matrix[0].length;
int maxCovered = 0;
for (int i = 0; i < (1 << n); i++) {
if (Integer.bitCount(i) == numSelect) {
int covered = 0;
for (int r = 0; r < m; r++) {
boolean isCovered = true;
for (int c = 0; c < n; c++) {
if (matrix[r][c] == 1 && ((i & (1 << c)) == 0)) {
isCovered = false;
break;
}
}
if (isCovered) covered++;
}
maxCovered = Math.max(maxCovered, covered);
}
}
return maxCovered;
}
public static void main(String[] args) {
int[][] matrix = {{0,0,0},{1,0,1},{0,1,1},{0,0,1}};
int numSelect = 2;
System.out.println(maxRowsCovered(matrix, numSelect));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxRowsCovered(const std::vector<std::vector<int>>& matrix, int numSelect) {
int m = matrix.size();
int n = matrix[0].size();
int maxCovered = 0;
std::vector<int> indices(n);
std::iota(indices.begin(), indices.end(), 0);
std::vector<int> selection(numSelect);
do {
std::copy(indices.begin(), indices.begin() + numSelect, selection.begin());
int covered = 0;
for (const auto& row : matrix) {
bool isCovered = true;
for (int j = 0; j < n; ++j) {
if (row[j] == 1 && std::find(selection.begin(), selection.end(), j) == selection.end()) {
isCovered = false;
break;
}
}
if (isCovered) ++covered;
}
maxCovered = std::max(maxCovered, covered);
} while (std::next_permutation(indices.begin(), indices.end()));
return maxCovered;
}
int main() {
std::vector<std::vector<int>> matrix = {{0,0,0},{1,0,1},{0,1,1},{0,0,1}};
int numSelect = 2;
std::cout << maxRowsCovered(matrix, numSelect) << std::endl;
return 0;
}function maxRowsCovered(matrix, numSelect) {
const m = matrix.length;
const n = matrix[0].length;
let maxCovered = 0;
const combinations = 1 << n;
for (let i = 0; i < combinations; i++) {
if (i.toString(2).split('1').length - 1 === numSelect) {
let covered = 0;
for (let r = 0; r < m; r++) {
let isCovered = true;
for (let c = 0; c < n; c++) {
if (matrix[r][c] === 1 && (i & (1 << c)) === 0) {
isCovered = false;
break;
}
}
if (isCovered) covered++;
}
maxCovered = Math.max(maxCovered, covered);
}
}
return maxCovered;
}
const matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]];
const numSelect = 2;
console.log(maxRowsCovered(matrix, numSelect));#include <stdio.h>
#include <string.h>
int maxRowsCovered(int matrix[12][12], int m, int n, int numSelect) {
int combination = 1 << n; // Total possible combinations
int maxCovered = 0;
for (int i = 0; i < combination; ++i) {
if (__builtin_popcount(i) == numSelect) { // Check selected columns
int covered = 0;
for (int r = 0; r < m; ++r) {
int isCovered = 1;
for (int c = 0; c < n; ++c) {
if (matrix[r][c] == 1 && !(i & (1 << c))) {
isCovered = 0;
break;
}
}
if (isCovered) covered++;
}
if (covered > maxCovered) maxCovered = covered;
}
}
return maxCovered;
}
int main() {
int matrix[4][3] = {{0,0,0},{1,0,1},{0,1,1},{0,0,1}};
int m = 4, n = 3;
int numSelect = 2;
printf("%d\n", maxRowsCovered(matrix, m, n, numSelect));
return 0;
}using System;
using System.Linq;
class MaxRowsCovered {
static int MaxRowsCovered(int[][] matrix, int numSelect) {
int m = matrix.Length;
int n = matrix[0].Length;
int maxCovered = 0;
int combinations = 1 << n;
for (int i = 0; i < combinations; i++) {
if (Convert.ToString(i, 2).Where(c => c == '1').Count() == numSelect) {
int covered = 0;
for (int r = 0; r < m; r++) {
bool isCovered = true;
for (int c = 0; c < n; c++) {
if (matrix[r][c] == 1 && ((i & (1 << c)) == 0)) {
isCovered = false;
break;
}
}
if (isCovered) covered++;
}
maxCovered = Math.Max(maxCovered, covered);
}
}
return maxCovered;
}
static void Main() {
int[][] matrix = new int[][] {
new int[] { 0, 0, 0 },
new int[] { 1, 0, 1 },
new int[] { 0, 1, 1 },
new int[] { 0, 0, 1 }
};
int numSelect = 2;
Console.WriteLine(MaxRowsCovered(matrix, numSelect));
}
}This Python solution makes use of the itertools.combinations method to efficiently explore all possible selections of column sets. Each selection is checked to see how many rows are covered, and the maximum covered rows are calculated.
Time Complexity: O(n^numSelect * m * n), where n is the number of columns, and m is the number of rows. Space complexity is O(n) due to the storage of current combinations.
Approach 2: Optimized Backtracking
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.
def backtrack(matrix, numSelect, start, selected, mask, m, n):
global maxCovered
if selected == numSelect:
covered = 0
for row in matrix:
if all(row[c] == 0 or (mask & (1 << c)) for c in range(n)):
covered += 1
maxCovered = max(maxCovered, covered)
return
for i in range(start, n):
backtrack(matrix, numSelect, i + 1, selected + 1, mask | (1 << i), m, n)
matrix = [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 0, 1]]
numSelect = 2
maxCovered = 0
backtrack(matrix, numSelect, 0, 0, 0, len(matrix), len(matrix[0]))
print(maxCovered)public class MaxRowsCoveredBacktrack {
private static int maxCovered = 0;
private static void backtrack(int[][] matrix, int m, int n, int numSelect, int start, int selected, int mask) {
if (selected == numSelect) {
int covered = 0;
for (int[] row : matrix) {
boolean isCovered = true;
for (int c = 0; c < n; c++) {
if (row[c] == 1 && (mask & (1 << c)) == 0) {
isCovered = false;
break;
}
}
if (isCovered) covered++;
}
maxCovered = Math.max(maxCovered, covered);
return;
}
for (int i = start; i < n; ++i) {
backtrack(matrix, m, n, numSelect, i + 1, selected + 1, mask | (1 << i));
}
}
public static void main(String[] args) {
int[][] matrix = {{0, 0, 0}, {1, 0, 1}, {0, 1, 1}, {0, 0, 1}};
int numSelect = 2;
backtrack(matrix, matrix.length, matrix[0].length, numSelect, 0, 0, 0);
System.out.println(maxCovered);
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxCovered = 0;
void backtrack(const std::vector<std::vector<int>>& matrix, int m, int n, int numSelect, int start, int selected, int mask) {
if (selected == numSelect) {
int covered = 0;
for (const auto& row : matrix) {
bool isCovered = true;
for (int j = 0; j < n; ++j) {
if (row[j] == 1 && !(mask & (1 << j))) {
isCovered = false;
break;
}
}
if (isCovered) ++covered;
}
maxCovered = std::max(maxCovered, covered);
return;
}
for (int i = start; i < n; ++i) {
backtrack(matrix, m, n, numSelect, i + 1, selected + 1, mask | (1 << i));
}
}
int main() {
std::vector<std::vector<int>> matrix = {{0, 0, 0}, {1, 0, 1}, {0, 1, 1}, {0, 0, 1}};
int numSelect = 2;
backtrack(matrix, matrix.size(), matrix[0].size(), numSelect, 0, 0, 0);
std::cout << maxCovered << std::endl;
return 0;
}let maxCovered = 0;
function backtrack(matrix, numSelect, start, selected, mask) {
const m = matrix.length;
const n = matrix[0].length;
if (selected === numSelect) {
let covered = 0;
for (let r = 0; r < m; r++) {
let isCovered = true;
for (let c = 0; c < n; c++) {
if (matrix[r][c] === 1 && !(mask & (1 << c))) {
isCovered = false;
break;
}
}
if (isCovered) covered++;
}
maxCovered = Math.max(maxCovered, covered);
return;
}
for (let i = start; i < n; i++) {
backtrack(matrix, numSelect, i + 1, selected + 1, mask | (1 << i));
}
}
const matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]];
const numSelect = 2;
backtrack(matrix, numSelect, 0, 0, 0);
console.log(maxCovered);#include <stdio.h>
#include <string.h>
int maxCovered = 0;
void backtrack(int matrix[12][12], int m, int n, int numSelect, int start, int selected, int mask) {
if (selected == numSelect) {
int covered = 0;
for (int r = 0; r < m; ++r) {
int isCovered = 1;
for (int c = 0; c < n; ++c) {
if (matrix[r][c] == 1 && !(mask & (1 << c))) {
isCovered = 0;
break;
}
}
if (isCovered) covered++;
}
if (covered > maxCovered) maxCovered = covered;
return;
}
for (int i = start; i < n; ++i) {
backtrack(matrix, m, n, numSelect, i + 1, selected + 1, mask | (1 << i));
}
}
int main() {
int matrix[4][3] = {{0,0,0},{1,0,1},{0,1,1},{0,0,1}};
int m = 4, n = 3;
int numSelect = 2;
backtrack(matrix, m, n, numSelect, 0, 0, 0);
printf("%d\n", maxCovered);
return 0;
}using System;
class MaxRowsCoveredBacktrack {
static int maxCovered = 0;
static void Backtrack(int[][] matrix, int m, int n, int numSelect, int start, int selected, int mask) {
if (selected == numSelect) {
int covered = 0;
for (int r = 0; r < m; r++) {
bool isCovered = true;
for (int c = 0; c < n; c++) {
if (matrix[r][c] == 1 && ((mask & (1 << c)) == 0)) {
isCovered = false;
break;
}
}
if (isCovered) covered++;
}
maxCovered = Math.Max(maxCovered, covered);
return;
}
for (int i = start; i < n; ++i) {
Backtrack(matrix, m, n, numSelect, i + 1, selected + 1, mask | (1 << i));
}
}
static void Main() {
int[][] matrix = new int[][] {
new int[] { 0, 0, 0 },
new int[] { 1, 0, 1 },
new int[] { 0, 1, 1 },
new int[] { 0, 0, 1 }
};
int numSelect = 2;
Backtrack(matrix, matrix.Length, matrix[0].Length, numSelect, 0, 0, 0);
Console.WriteLine(maxCovered);
}
}This Python solution employs a recursive function to systematically approach combinations through incremental column selection. The function calculates the maximum number of covered rows and optimizes for early exits during recursive calls when any remaining columns can't overcome the current best coverage found.
Time Complexity: O(C(n, numSelect) * m * n) with C(n, numSelect) being the number of combinations. The space complexity is O(n) for recursion depth management.
Approach 3: Binary Enumeration
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.
function maximumRows(matrix: number[][], numSelect: number): number {
const [m, n] = [matrix.length, matrix[0].length];
const rows: number[] = Array(m).fill(0);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (matrix[i][j]) {
rows[i] |= 1 << j;
}
}
}
let ans = 0;
for (let mask = 1; mask < 1 << n; ++mask) {
if (bitCount(mask) !== numSelect) {
continue;
}
let t = 0;
for (const x of rows) {
if ((x & mask) === x) {
++t;
}
}
ans = Math.max(ans, t);
}
return ans;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func maximumRows(matrix [][]int, numSelect int) (ans int) {
m, n := len(matrix), len(matrix[0])
rows := make([]int, m)
for i, row := range matrix {
for j, x := range row {
if x == 1 {
rows[i] |= 1 << j
}
}
}
for mask := 1; mask < 1<<n; mask++ {
if bits.OnesCount(uint(mask)) != numSelect {
continue
}
t := 0
for _, x := range rows {
if (x & mask) == x {
t++
}
}
if ans < t {
ans = t
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Combinations | Time Complexity: O(n^numSelect * m * n), where n is the number of columns, and m is the number of rows. Space complexity is O(n) due to the storage of current combinations. |
| Optimized Backtracking | Time Complexity: O(C(n, numSelect) * m * n) with C(n, numSelect) being the number of combinations. The space complexity is O(n) for recursion depth management. |
| Binary Enumeration | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Maximum Rows Covered by Columns easy or hard?
Maximum Rows Covered by Columns is generally classified as a Medium difficulty problem. The brute force idea is straightforward, but recognizing the bitmask optimization and implementing efficient subset enumeration requires familiarity with backtracking and bit manipulation.
Maximum Rows Covered by Columns Python/Java solution
Python and Java solutions typically implement backtracking to generate column subsets and store row patterns as bitmasks. The coverage check uses (rowMask & selectedMask) == rowMask, which ensures that every 1 in the row is included in the chosen columns.
How to solve Maximum Rows Covered by Columns in O(n)?
A strict O(n) solution is not possible because the problem requires evaluating combinations of selected columns. The best practical solution enumerates column subsets using backtracking and evaluates coverage using bit masks, resulting in O(C(n,k) * m) time.
What is the best approach for Maximum Rows Covered by Columns?
The most effective approach uses backtracking combined with bit manipulation. Each row is converted into a bitmask, and column selections are represented as another mask. A row is covered if (rowMask & selectedMask) equals rowMask. This reduces row validation to constant time, giving a complexity of O(C(n,k) * m).
Is Maximum Rows Covered by Columns asked at Google/Amazon/Meta?
Matrix enumeration and bitmask problems like this appear in interviews at companies such as Google, Amazon, and Meta. Variants involving subset selection, bitmask optimization, or matrix coverage are commonly used to evaluate combinational search and optimization skills.
What data structure is used in Maximum Rows Covered by Columns?
The core data structure is a bitmask representation of rows and selected columns. The matrix rows are encoded as integers, and bitwise operations are used to quickly check if a row's required columns are included in the selected set.
What is the time complexity of Maximum Rows Covered by Columns?
The optimized solution runs in O(C(n,k) * m), where n is the number of columns, k is numSelect, and m is the number of rows. Each column subset is generated using backtracking, and each row is checked using a constant-time bitwise comparison.