Maximum Rows Covered by Columns
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 1s 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 selected = {c1, c2, ..., cnumSelect} be 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
0 0 0 1 0 1 0 1 1 0 0 1
Input
matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2Output
3Choosing columns 0 and 2 covers rows 0, 1, and 3, and no selection can cover more than three rows.
Example 2
1 0
Input
matrix = [[1],[0]], numSelect = 1Output
2Selecting the only column covers the entire matrix, so both rows are covered.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 12
- matrix[i][j] is either 0 or 1.
- 1 <= numSelect <= n
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.