Maximum Rows Covered by Columns - Practice Coding Problems

Maximum Rows Covered by Columns - 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 column j is in selected.
Or, no cell in row i has a value of 1.

Return the maximum number of rows that can be covered by a set of numSelect columns.

Input & Output

Example 1 — Basic Coverage

$ Input: matrix = [[0,0,0],[1,0,1]], numSelect = 2

› Output: 2

💡 Note: Select columns [0,2]: Row 0 has no 1s (covered), Row 1 has 1s at positions 0,2 which are both selected (covered). Total: 2 rows.

Example 2 — Partial Coverage

$ Input: matrix = [[1],[0]], numSelect = 1

› Output: 2

💡 Note: Select column [0]: Row 0 has 1 at position 0 (covered), Row 1 has no 1s (covered). Both rows covered.

Example 3 — Impossible Full Coverage

$ Input: matrix = [[1,0],[0,1]], numSelect = 1

› Output: 1

💡 Note: Can only select 1 column. Either column covers exactly 1 row, so maximum is 1.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 12
matrix[i][j] is either 0 or 1
1 ≤ numSelect ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with rows containing 0s and 1s

Column Selection

Choose exactly numSelect columns to maximize coverage

Coverage Count

Count rows where all 1s are in selected columns

Key Takeaway

🎯 Key Insight: Convert the problem to finding optimal column combinations using bit manipulation for efficient row coverage checking

Asked in

G Google 12 M Microsoft 8 a Amazon 6 f Meta 4

The key insight is to recognize this as a combinatorial optimization problem where we need to find the optimal subset of columns. The bit manipulation approach provides the most efficient solution by converting rows to bitmasks for O(1) coverage checking. Best approach: Bit Manipulation - Time: O(2ⁿ × m), Space: O(m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(C(n,k) × m × n)	O(k)	Generate all possible combinations of numSelect columns and count covered rows for each
Backtracking with Pruning	O(2^n)	O(n)	Use backtracking to explore column combinations with early pruning when impossible to beat current best
Bit Manipulation Optimization	O(C(n,k) × m)	O(m)	Convert rows to bitmasks and use bitwise operations for efficient row coverage checking

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all combinations of numSelect columns from available columns
Step 2: For each combination, count how many rows are covered
Step 3: Return the maximum count found across all combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all ways to choose numSelect columns

Check Coverage

For each combination, count covered rows

Find Maximum

Return the best combination's coverage

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** matrix, int m, int n, int numSelect) {
    int maxCovered = 0;
    
    // Simple brute force with bit manipulation for combinations
    int totalCols = 1 << n;
    
    for (int mask = 0; mask < totalCols; mask++) {
        if (__builtin_popcount(mask) != numSelect) continue;
        
        int coveredRows = 0;
        
        // Check each row
        for (int i = 0; i < m; i++) {
            int isCovered = 1;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1 && !(mask & (1 << j))) {
                    isCovered = 0;
                    break;
                }
            }
            if (isCovered) coveredRows++;
        }
        
        if (coveredRows > maxCovered) {
            maxCovered = coveredRows;
        }
    }
    
    return maxCovered;
}

int main() {
    // Simple matrix parsing for demonstration
    int m = 2, n = 3;
    int** matrix = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        matrix[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Example: [[0,0,0],[1,0,1]]
    matrix[0][0] = 0; matrix[0][1] = 0; matrix[0][2] = 0;
    matrix[1][0] = 1; matrix[1][1] = 0; matrix[1][2] = 1;
    
    int numSelect = 2;
    
    printf("%d\n", solution(matrix, m, n, numSelect));
    
    // Cleanup
    for (int i = 0; i < m; i++) {
        free(matrix[i]);
    }
    free(matrix);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(n,k) × m × n)

C(n,k) combinations where each requires checking m rows and n columns

✓ Linear Growth

Space Complexity

O(k)

Only stores current combination of k selected columns

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

285 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler