We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Rows Covered by Columns

Number: 2482

Difficulty: Medium

Paid? No

Companies: Apple

Problem Description

Given an m x n binary matrix and an integer numSelect, the goal is to select exactly numSelect distinct columns to maximize the number of covered rows. A row is considered covered if every cell containing a 1 has its corresponding column selected. Additionally, rows with no 1’s are automatically covered.

Key Insights

  • Use bitmasks to represent rows and selected columns since n (the number of columns) is at most 12.
  • Precompute a bitmask for each row where each bit represents if that column has a 1.
  • Enumerate over all possible combinations of columns (bitmask with exactly numSelect bits set).
  • For each combination, check each row: a row is covered if the row’s bitmask is a subset of the selected columns’ bitmask.
  • Due to small constraints (m, n ≤ 12), this brute-force enumeration approach is efficient.

Space and Time Complexity

Time Complexity: O(Combination(n, numSelect) * m)
Space Complexity: O(m) (for storing the bitmask of each row)

Solution

We precompute a bitmask for each row where each bit is set if the corresponding column has a 1. Then, we generate every possible subset of columns (as a bitmask) that contains exactly numSelect bits. For each subset, we check how many rows are covered by verifying that for each row, the row’s bitmask is a subset of the selected columns bitmask (i.e. bitwise AND equals the row’s bitmask). The maximum number of covered rows across all subsets is our answer.

Code Solutions

# Python solution using itertools.combinations for generating column combinations

from itertools import combinations

def maximumRows(matrix, numSelect):
    m = len(matrix)
    n = len(matrix[0])
    
    # Precompute the bitmask for each row
    row_masks = []
    for row in matrix:
        mask = 0
        for j, val in enumerate(row):
            if val == 1:
                mask |= (1 << j)
        row_masks.append(mask)
    
    max_covered = 0
    # Generate all combinations of columns indices of size numSelect
    for cols in combinations(range(n), numSelect):
        # Create bitmask for the selected columns
        selected_mask = 0
        for col in cols:
            selected_mask |= (1 << col)
        
        # Count how many rows are covered by the selected columns
        covered = 0
        for mask in row_masks:
            # A row is covered if all 1's in the row are in selected_mask.
            if mask & selected_mask == mask:
                covered += 1
        
        max_covered = max(max_covered, covered)
    return max_covered

# Example usage:
if __name__ == "__main__":
    matrix = [[0,0,0], [1,0,1], [0,1,1], [0,0,1]]
    numSelect = 2
    print(maximumRows(matrix, numSelect))  # Expected output: 3
← Back to All Questions