Maximum Rows Covered by Columns

Maximum Rows Covered by Columns

1. What is this problem about?

The Maximum Rows Covered by Columns interview question is a matrix optimization problem. You are given a binary matrix and an integer numSelect. You need to choose exactly numSelect columns to "cover." A row is considered "covered" if all the 1s in that row are in the selected columns. The goal is to maximize the number of covered rows.

This is a selection problem where the number of columns is usually small (up to 12-15), making it possible to explore all combinations of column selections.

2. Why is this asked in interviews?

Apple and other companies ask the Maximum Rows Covered by Columns coding problem to evaluate a candidate's ability to use bitmasks and combinatorial search. It tests whether you can recognize that since the column count is small, you can represent each row as a bitmask. It also assesses your ability to generate combinations or use bitwise logic to quickly check if a row's 1s are a subset of the selected columns.

3. Algorithmic pattern used

The Array, Matrix, Enumeration, Backtracking, Bit Manipulation interview pattern is the way to solve this.

1. Convert each row of the matrix into a bitmask (an integer where the i-th bit is 1 if matrix[row][i] is 1).
2. Generate all possible combinations of numSelect columns out of total columns C.
3. For each combination, create a "selection mask."
4. A row is covered if (row_mask & selection_mask) == row_mask.
5. Count the covered rows for each combination and return the maximum.

4. Example explanation

Matrix: [1, 0] [0, 1] [1, 1] numSelect = 1.

• Choose Column 0: Selection mask = 10 (binary).
  • Row 0 (10): (10 & 10) == 10. Covered.
  • Row 1 (01): (01 & 10) == 0. Not covered.
  • Row 2 (11): (11 & 10) == 10 != 11. Not covered.
  • Total: 1.
• Choose Column 1: Selection mask = 01 (binary).
  • Row 0 (10): Not covered.
  • Row 1 (01): Covered.
  • Row 2 (11): Not covered.
  • Total: 1. Max rows covered: 1.

5. Common mistakes candidates make

In the Maximum Rows Covered by Columns coding problem, a frequent error is using a complex backtracking solution when a simple bitmask iteration over all integers with numSelect bits set would be faster. Another mistake is not correctly converting rows to masks or misinterpreting the "covered" condition (thinking only 1s matter, which is correct, but the logic must be precise).

6. Interview preparation tip

Practice using (1 << i) to set bits and __builtin_popcount (in C++) or similar functions to count set bits. Being comfortable with "subset" checks using bitwise operations ((a & b) == a) is a very common requirement in matrix and set-based optimization problems.