Maximum Rows Covered by Columns

Medium

Asked by:

22 views

Topics:

Bit ManipulationArrays

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 = {c₁, c₂, ...., c_numSelect} 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.

Example 1:

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

Output: 3

Explanation:

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

Explanation:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what are the possible values within the matrix and the integer k?
Can a row contain duplicate elements, and if so, does that affect whether it is considered 'covered'?
If no combination of columns can cover at least one row, what should I return?
Is the order of the selected columns important? Are we looking for any valid combination, or a specific combination based on some criteria (e.g., lexicographically smallest)?
Can k be larger than the number of columns in the matrix?

Brute Force Solution

Approach

The brute force approach to this problem means trying every single possible combination of columns that we are allowed to keep. For each of these combinations, we then check how many rows are fully covered by the columns we chose.

Here's how the algorithm would work step-by-step:

First, think about all the different groups of columns you could possibly pick.
For example, if you can pick 2 columns, try picking columns 1 and 2, then columns 1 and 3, then columns 2 and 3, and so on, until you've tried all possible pairs.
For each group of columns you pick, look at each row in the data.
Check if every '1' in that row appears in one of the columns you picked.
If all the '1's in a row are in your picked columns, that row is 'covered'.
Count how many rows are covered by your chosen columns.
Repeat this process for every single possible group of columns.
Finally, compare the number of covered rows for all the different groups of columns you tried.
The group of columns that covers the most rows is your answer.

Code Implementation

def maximum_rows_covered_by_columns_brute_force(matrix, number_of_columns_to_select):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    maximum_covered_rows = 0

    # Iterate through all possible combinations of columns
    for combination_index in range(1 << number_of_columns):
        if bin(combination_index).count('1') == number_of_columns_to_select:
            selected_columns = []

            for column_index in range(number_of_columns):
                if (combination_index >> column_index) & 1:
                    selected_columns.append(column_index)

            covered_rows_count = 0
            # Check how many rows are covered by the selected columns
            for row_index in range(number_of_rows):
                is_row_covered = True

                for column_index in range(number_of_columns):
                    # Check if a '1' exists in this row and column
                    if matrix[row_index][column_index] == 1:
                        # Ensure the '1' is in one of the selected columns
                        if column_index not in selected_columns:
                            is_row_covered = False
                            break

                if is_row_covered:
                    covered_rows_count += 1

            # Update the maximum number of covered rows
            maximum_covered_rows = max(maximum_covered_rows, covered_rows_count)

    return maximum_covered_rows

Big(O) Analysis

Time Complexity

O(C(M, K) * N * M) – The algorithm iterates through all possible combinations of K columns out of M columns, which takes C(M, K) time where C(M, K) represents the binomial coefficient (M choose K). For each combination of columns, the algorithm iterates through each of the N rows. For each row, it iterates up to M columns (the number of columns in the original matrix) to determine if the row is covered. Thus the time complexity can be expressed as O(C(M, K) * N * M), where N is the number of rows, M is the number of columns, and K is the number of columns to choose.

Space Complexity

O(1) – The brute force approach, as described, primarily involves iterating through combinations and checking coverage without significant auxiliary data structures. While column combinations are generated, they are likely processed one at a time without storing all combinations simultaneously. The space is dominated by a few variables to keep track of row and column indices, and the maximum number of covered rows, which remains constant regardless of the input matrix size (number of rows and columns). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem asks us to select a limited number of columns to maximize the number of fully covered rows in a grid. We'll use a clever way to try all possible column combinations efficiently, avoiding the need to check every single one.

Here's how the algorithm would work step-by-step:

First, recognize that each possible combination of selected columns can be represented as a binary number.
Think of each column as corresponding to a bit in a number. If the bit is 'on' (1), the column is selected; if it's 'off' (0), it's not.
We can then go through all possible combinations of columns by counting from 0 up to a maximum value, where each value represents a different set of selected columns.
For each combination, we need to check how many rows are fully covered by the selected columns.
A row is covered if, for every column that's *not* selected, the corresponding cell in that row has a zero.
Keep track of the maximum number of covered rows you find as you try different combinations.
After going through all possible combinations of columns, the maximum number of covered rows that you kept track of is the answer.

Code Implementation

def maximum_rows_covered(grid, number_of_columns_to_select):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    maximum_covered_rows = 0

    # Iterate through all possible column combinations
    for column_combination_mask in range(2**number_of_columns):
        
        #Check that this combination has the correct number of columns selected
        if bin(column_combination_mask).count('1') == number_of_columns_to_select:
            covered_rows_count = 0

            for row_index in range(number_of_rows):
                is_row_covered = True
                
                # Check if the row is covered by the selected columns
                for column_index in range(number_of_columns):
                    # If the column is not selected...
                    if not (column_combination_mask & (1 << column_index)):

                        # ... and the row has a 1 in that column, it's not covered.
                        if grid[row_index][column_index] == 1:
                            is_row_covered = False
                            break

                # Increment the count if the row is fully covered
                if is_row_covered:
                    covered_rows_count += 1

            #Update the maximum covered rows if needed
            maximum_covered_rows = max(maximum_covered_rows, covered_rows_count)

    return maximum_covered_rows

Big(O) Analysis

Time Complexity

O(2^m * n * m) – The outer loop iterates through all possible combinations of columns. Since there are m columns, there are 2^m possible combinations. Inside this loop, we iterate through n rows to check if each row is covered. For each row, we iterate through all the columns (m) to determine if it's covered based on the selected columns in the current combination. Therefore, the time complexity is approximately 2^m * n * m, which simplifies to O(2^m * n * m).

Space Complexity

O(1) – The algorithm iterates through column combinations and rows, calculating covered rows. It uses a few integer variables to store the current column combination, the maximum covered rows found so far, and potentially a counter for covered rows in the current combination. The space required for these variables is constant and independent of the size of the input grid (number of rows or columns). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty matrix (rows or cols = 0)	Return 0 if either rows or cols is zero since no rows can be covered.
k is 0	Return 0, as no columns are selected to cover rows.
k is greater than number of columns	Return number of rows since selecting all columns will cover all rows.
Matrix with all 0s	Return number of rows since any choice of columns will cover all rows.
Matrix with all 1s	Selecting any k columns will cover all rows, so return the number of rows.
Large matrix dimensions (performance)	Use bitmasking and efficient bitwise operations to represent rows and column selections for optimal performance.
Rows with identical coverage patterns	The algorithm should correctly count these rows only once when their coverage requirements are met.
No combination of k columns can cover any rows	The algorithm will correctly return 0, as no rows can be fully covered.

Empty matrix (rows or cols = 0)

How to Handle:

Return 0 if either rows or cols is zero since no rows can be covered.

k is 0

How to Handle:

Return 0, as no columns are selected to cover rows.

k is greater than number of columns

How to Handle:

Return number of rows since selecting all columns will cover all rows.

Matrix with all 0s

How to Handle:

Return number of rows since any choice of columns will cover all rows.

Matrix with all 1s

How to Handle:

Selecting any k columns will cover all rows, so return the number of rows.

Large matrix dimensions (performance)

How to Handle:

Use bitmasking and efficient bitwise operations to represent rows and column selections for optimal performance.

Rows with identical coverage patterns

How to Handle:

The algorithm should correctly count these rows only once when their coverage requirements are met.

No combination of k columns can cover any rows

How to Handle:

The algorithm will correctly return 0, as no rows can be fully covered.