Problem Description

You are given a 0-indexed m x n binary matrix grid where each element is either 0 or 1.

The task is to find a good subset of rows from this matrix. A subset of rows is considered good if it satisfies the following condition:

• For every column in the selected subset of rows, the sum of that column's values must be at most half of the number of rows in the subset.
• Mathematically, if you select k rows, then for each column, the sum of the k values in that column must be at most floor(k/2).

For example:

• If you select 1 row, each column sum must be at most floor(1/2) = 0
• If you select 2 rows, each column sum must be at most floor(2/2) = 1
• If you select 3 rows, each column sum must be at most floor(3/2) = 1
• If you select 4 rows, each column sum must be at most floor(4/2) = 2

You need to return an array containing the row indices of any good subset, sorted in ascending order. If multiple good subsets exist, you can return any one of them. If no good subset exists, return an empty array.

The key insight from the solution is that only subsets of size 1 or 2 can possibly be good:

• For k = 1: The only way to satisfy the condition is if the selected row contains all 0s (since each column sum must be 0).
• For k = 2: The two selected rows must have no column where both rows have a 1 (their bitwise AND must be 0), ensuring each column sum is at most 1.
• For k ≥ 3: It can be proven that no valid subset exists due to the constraints on column sums and the limited number of columns (at most 5).

Intuition

The key insight comes from analyzing what values of k (number of selected rows) can actually satisfy the constraint.

Let's think about this systematically. For a subset of k rows to be good, each column sum must be at most floor(k/2). This means:

• When k = 1: column sum ≤ 0, so the row must be all zeros
• When k = 2: column sum ≤ 1, so at most one 1 per column
• When k = 3: column sum ≤ 1, still at most one 1 per column
• When k = 4: column sum ≤ 2, so at most two 1s per column

Here's the crucial observation: if we can't find a valid subset for k = 2, we definitely can't find one for k = 3. Why? Because with 3 rows and the same constraint (column sum ≤ 1), we need an even stricter condition - essentially, the three rows must be "compatible" in a way that no column has more than one 1. But if no two rows satisfy this condition, adding a third row won't help.

For k = 4, even though the constraint relaxes to allowing 2 ones per column, we run into a counting problem. If no two rows have bitwise AND equal to 0 (meaning every pair of rows has at least one column where both have 1s), then when we pick 4 rows, we're choosing C(4,2) = 6 pairs. Each pair contributes at least one column with sum ≥ 2. Since the matrix has at most 5 columns, by the pigeonhole principle, at least one column must have sum > 2, violating our constraint.

This pattern continues for larger k values. The constraints become impossible to satisfy when we can't even find 2 rows that work together.

Therefore, we only need to check:

1. Is there a single row with all zeros?
2. Are there two rows whose bitwise AND equals 0?

The solution cleverly uses bit manipulation where each row is represented as a bitmask (integer), making it efficient to check if two rows have no overlapping 1s by testing if (mask1 & mask2) == 0.

Solution Approach

The solution implements the case analysis strategy by checking for valid subsets of size 1 and 2.

Step 1: Convert rows to bitmasks and check for all-zero rows

We iterate through each row and convert it to a bitmask representation. For each row i:

• Initialize mask = 0
• For each column j with value x, we set the j-th bit of the mask using mask |= x << j
• If mask == 0, it means the entire row contains only zeros, so we immediately return [i] as this single row forms a good subset

Step 2: Store unique masks with their row indices

We use a dictionary g where:

• Key: the bitmask representation of a row
• Value: the row index

This ensures we only keep one row index for each unique bit pattern, which is sufficient since we only need to find any valid subset.

Step 3: Find two rows with bitwise AND equal to 0

We perform a nested iteration over all pairs of masks in the dictionary:

• For each pair (a, i) and (b, j) where a and b are masks and i, j are row indices
• Check if (a & b) == 0, which means the two rows have no column where both have a 1
• If found, return the sorted pair [i, j]

Step 4: Return empty array if no valid subset found

If we've checked all possibilities and found no valid subset, return an empty array.

Time Complexity: O(m × n + U²) where m is the number of rows, n is the number of columns, and U is the number of unique row patterns (at most 2^n).

Space Complexity: O(U) for storing the dictionary of unique masks.

The brilliance of this approach lies in recognizing that we only need to consider small subset sizes and using bit manipulation for efficient checking of row compatibility.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Consider the following 4×3 binary matrix:

grid = [[0,1,1],
        [1,0,1],
        [0,0,0],
        [1,1,0]]

Step 1: Convert rows to bitmasks and check for all-zero rows

We process each row and convert it to a bitmask:

• Row 0: [0,1,1] → mask = 0|1<<1|1<<2 = 0|2|4 = 6 (binary: 110)
• Row 1: [1,0,1] → mask = 1<<0|0|1<<2 = 1|0|4 = 5 (binary: 101)
• Row 2: [0,0,0] → mask = 0|0|0 = 0 (binary: 000)
  • Found an all-zero row! Return [2] immediately.

The algorithm would stop here and return [2] as the answer, since row 2 contains all zeros and forms a valid subset of size 1.

Alternative scenario: Let's modify the example to see the full algorithm:

grid = [[0,1,1],
        [1,0,1],
        [1,0,0],
        [1,1,0]]

Step 1: Convert and check for zeros

• Row 0: [0,1,1] → mask = 6 (binary: 110)
• Row 1: [1,0,1] → mask = 5 (binary: 101)
• Row 2: [1,0,0] → mask = 1 (binary: 001)
• Row 3: [1,1,0] → mask = 3 (binary: 011)

No all-zero rows found, so we continue.

Step 2: Store unique masks Dictionary g:

• 6 → row index 0
• 5 → row index 1
• 1 → row index 2
• 3 → row index 3

Step 3: Find two compatible rows Check all pairs for (mask1 & mask2) == 0:

• Masks 6 and 5: 110 & 101 = 100 (not 0)
• Masks 6 and 1: 110 & 001 = 000 ✓ Found a valid pair!
  • Rows 0 and 2 have no overlapping 1s
  • Return sorted indices: [0, 2]

Let's verify this answer:

• Selected rows: [0,1,1] and [1,0,0]
• Column sums: [0+1=1, 1+0=1, 1+0=1]
• All column sums ≤ floor(2/2) = 1 ✓

The algorithm successfully found a good subset of size 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n + 4^n)

The time complexity consists of two main parts:

• O(m × n): Building the bitmask for each row requires iterating through all m rows and for each row, iterating through all n columns to construct the mask.
• O(4^n): In the worst case, we need to check all pairs of masks stored in the dictionary g. Since each column can either be 0 or 1, and we're storing unique masks, there can be at most 2^n different masks. Checking all pairs would be O((2^n)^2) = O(4^n).

Space Complexity: O(2^n)

The space complexity is determined by the dictionary g which stores the mapping from masks to row indices. Since each mask is an n-bit number representing a unique combination of 0s and 1s across n columns, there can be at most 2^n different masks stored in the dictionary.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Checking the Same Row Twice

Issue: The nested loop checks all pairs including when bitmask_a and bitmask_b refer to the same row. When a row is paired with itself, the condition (bitmask_a & bitmask_b) == 0 would only be true if the row contains all zeros, but we've already handled that case. This creates an edge case where the same row index could appear twice in the result.

Example: If we have a row of all zeros that wasn't caught in the first check (though this shouldn't happen with correct implementation), the code might return [i, i] which is invalid.

Solution: Add a check to ensure we're not comparing a row with itself:

for bitmask_a, row_index_a in bitmask_to_row.items():
    for bitmask_b, row_index_b in bitmask_to_row.items():
        # Skip if comparing the same row
        if row_index_a >= row_index_b:
            continue
        if (bitmask_a & bitmask_b) == 0:
            return sorted([row_index_a, row_index_b])

Pitfall 2: Overwriting Row Indices in the Dictionary

Issue: Multiple rows might have the same bitmask pattern. The current implementation overwrites the previous row index when encountering a duplicate pattern, potentially missing valid pairs.

Example:

• Row 0: [1, 0, 0] → bitmask = 1
• Row 2: [1, 0, 0] → bitmask = 1 (overwrites row 0)
• Row 3: [0, 1, 1] → bitmask = 6

The code would miss the valid pair [0, 3] because row 0's index was overwritten.

Solution: Store all row indices for each bitmask pattern:

# Dictionary to store all row indices for each bitmask
bitmask_to_rows = defaultdict(list)

for row_index, row in enumerate(grid):
    bitmask = 0
    for col_index, value in enumerate(row):
        bitmask |= value << col_index
  
    if bitmask == 0:
        return [row_index]
  
    bitmask_to_rows[bitmask].append(row_index)

# Check pairs from different bitmask groups
for bitmask_a, rows_a in bitmask_to_rows.items():
    for bitmask_b, rows_b in bitmask_to_rows.items():
        if (bitmask_a & bitmask_b) == 0:
            # Return the first valid pair
            if bitmask_a != bitmask_b:
                return sorted([rows_a[0], rows_b[0]])

Pitfall 3: Inefficient Duplicate Pair Checking

Issue: The nested loop checks pairs (a, b) and later (b, a), which is redundant since bitwise AND is commutative.

Solution: Optimize by only checking each unique pair once:

masks_list = list(bitmask_to_row.items())
for i in range(len(masks_list)):
    for j in range(i, len(masks_list)):
        bitmask_a, row_index_a = masks_list[i]
        bitmask_b, row_index_b = masks_list[j]
        if (bitmask_a & bitmask_b) == 0:
            if i == j:  # Same bitmask group
                continue
            return sorted([row_index_a, row_index_b])