Maximum Rows Covered by Columns

Medium
1336.

Maximum Rows Covered by Columns

Maximum Rows Covered by Columns is a medium coding problem on arrays, matrix and bit manipulation, asked in Amazon and Google interviews.

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.length
  • n == matrix[i].length
  • 1 <= m, n <= 12
  • matrix[i][j] is either 0 or 1
  • 1 <= numSelect <= n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @param {number} numSelect
 * @return {number}
 */
var maximumRows = function(matrix, numSelect) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == matrix[i].length
  • 1 <= m, n <= 12
  • matrix[i][j] is either 0 or 1
  • 1 <= numSelect <= n

Hints for Maximum Rows Covered by Columns

  1. Hint 1

    There are at most 2^12 = 4096 ways to choose columns — enumerate them.

  2. Hint 2

    Turn each row into a bitmask of its 1-columns, and each selection into a bitmask too.

  3. Hint 3

    A row with mask r is covered by selection s exactly when r AND NOT s == 0. Try every s with numSelect bits 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

  1. Encode each row as rows[i], the mask of columns where it holds a 1.
  2. For every mask s from 0 to 2^n - 1 whose popcount equals numSelect:
  3. 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 numSelect columns 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 best

Java

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