Start by considering all possible combinations of columns using a backtracking search with pruning to avoid unnecessary exploration. Represent rows and selected columns using bit manipulation for fast coverage checks. This approach ensures you identify the selection that maximizes the number of fully covered rows without testing redundant column combinations.
Problem Statement
You are given an m x n binary matrix and an integer numSelect. Your task is to choose exactly numSelect distinct columns to maximize the number of rows that are covered.
A row is covered if every 1 in that row corresponds to a selected column. Rows with no ones are automatically covered. Determine the maximum count of covered rows that can be achieved with exactly numSelect columns.
Examples
Example 1
Input: matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
Output: 3
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
Selecting the only column will result in both rows being covered since the entire matrix is selected.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 12
- matrix[i][j] is either 0 or 1.
- 1 <= numSelect <= n
Solution Approach
Backtracking with Pruning
Generate all combinations of numSelect columns recursively, and prune paths where remaining columns cannot exceed the current best coverage.
Bitmask Representation
Use bitmask integers to represent which columns are selected and which ones exist in each row. This allows O(1) checks for whether a row is covered.
Counting Covered Rows Efficiently
For each valid selection of columns, iterate through rows using bit operations to count how many are fully covered. Update the maximum accordingly.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(C(n, numSelect) * m) due to generating combinations of columns and checking all rows. Space complexity is O(m) for storing bitmasks and recursion stack usage during backtracking.
What Interviewers Usually Probe
- Checks if you understand recursive backtracking with pruning.
- Tests efficient row coverage checks using bit manipulation.
- Wants candidates to reason about combinatorial limits and avoid unnecessary computation.
Common Pitfalls or Variants
Common pitfalls
- Not handling rows with all zeros correctly, which are automatically covered.
- Inefficiently checking row coverage without bitmasking, causing timeouts.
- Failing to prune column combinations that cannot improve the current maximum.
Follow-up variants
- Maximize rows covered when selecting up to numSelect columns instead of exactly.
- Find the minimum number of columns needed to cover all rows.
- Optimize coverage when matrix dimensions are larger and require advanced pruning.
How GhostInterview Helps
- Automatically tracks combinations and prunes impossible paths to reduce manual trial-and-error.
- Uses bitmask techniques to quickly check row coverage without nested loops.
- Provides step-by-step insights on which column selections maximize covered rows.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern in Maximum Rows Covered by Columns?
The main pattern is backtracking search with pruning to explore combinations efficiently.
Can I use bit manipulation to speed up coverage checks?
Yes, representing selected columns and row ones as bitmasks allows O(1) coverage checks.
How do I handle rows with no ones?
Rows with no ones are considered covered automatically and do not require any columns.
Is a brute-force approach viable for larger matrices?
For matrices up to 12x12, brute-force with pruning works, but larger matrices need optimized pruning or heuristics.
How does GhostInterview assist with this problem?
GhostInterview tracks combinations, prunes impossible selections, and calculates row coverage efficiently using bit operations.
Need direct help with Maximum Rows Covered by Columns instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Maximum Rows Covered by Columns from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
In the "Maximum Points in an Archery Competition" problem, Bob aims to maximize his score while respecting Alice's arrow counts.
Open problem page#2151 Maximum Good People Based on StatementsDetermine the maximum number of good people in a group given mutual statements, using precise backtracking with pruning.
Open problem page#2708 Maximum Strength of a GroupMaximize the strength of a student group by carefully selecting students based on their scores, using dynamic programming and state transitions.
Open problem page