Find a Good Subset of the Matrix

• Generate all 2^m - 1 non-empty subsets of row indices. This can be done by iterating a counter from 1 to 2^m - 1 and using its binary representation to select rows.
• For each subset of size k:
  • For each column j from 0 to n-1, calculate the sum of its elements over the rows in the subset.
  • If the sum for any column j is greater than floor(k/2), this subset is not good. Move to the next subset.
  • If all column sums satisfy the condition, a good subset has been found. Return its row indices, sorted in ascending order.
• If the loop finishes without finding any good subset, it means none exists. Return an empty array.

The most straightforward way to solve this problem is to exhaustively check all possibilities. We can represent a subset of rows using a bitmask of length m. Each bit in the mask corresponds to a row, and if the bit is set, the row is included in the subset. We iterate through all possible masks from 1 to 2^m - 1 (excluding the empty set). For each mask, we form the corresponding subset of rows and verify if it's a "good" subset by checking the sum of each column against the condition. The first good subset we find is a valid answer.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {6        int m = grid.length;7        int n = grid[0].length;8 9        // Iterate through all 2^m - 1 non-empty subsets of rows10        for (int i = 1; i < (1 << m); i++) {11            List<Integer> subsetIndices = new ArrayList<>();12            int k = 0; // Size of the subset13            for (int j = 0; j < m; j++) {14                // Check if the j-th row is in the current subset15                if ((i & (1 << j)) != 0) {16                    subsetIndices.add(j);17                    k++;18                }19            }20 21            if (isGood(grid, subsetIndices, k, n)) {22                return subsetIndices; // Found a good subset23            }24        }25 26        return new ArrayList<>(); // No good subset found27    }28 29    private boolean isGood(int[][] grid, List<Integer> subset, int k, int n) {30        if (k == 0) {31            return false;32        }33        for (int j = 0; j < n; j++) {34            int colSum = 0;35            for (int rowIndex : subset) {36                colSum += grid[rowIndex][j];37            }38            if (colSum > k / 2) {39                return false; // Condition failed for this column40            }41        }42        return true; // All columns satisfy the condition43    }44}

• The core idea is that if any good subset exists, a good subset of size 1 or 2 must also exist.
• Check for size 1: A single row i is a good subset if it contains all zeros. The condition is sum <= floor(1/2) = 0.
• Check for size 2: A pair of rows i and p is a good subset if for every column, grid[i][j] + grid[p][j] <= floor(2/2) = 1. This is true if and only if the bitwise AND of their corresponding masks is 0.
• Algorithm Steps:
  1. Create a map to store the first seen index for each unique row mask (mask -> rowIndex).
  2. Iterate through each row i of the grid.
  3. Convert the row to its integer bitmask representation.
  4. If the mask is 0, we've found a size-1 good subset. Return [i] immediately.
  5. Store the mask and index i in the map.
  6. After iterating through all rows (if no all-zero row was found), iterate through all pairs of unique masks present in the map.
  7. For any pair of masks (m1, m2) such that (m1 & m2) == 0, retrieve their original indices and return them as the answer, sorted.
  8. If no such pair is found, no good subset of size 1 or 2 exists, which implies no good subset of any size exists. Return an empty array.

We can significantly improve efficiency by focusing our search. A subset of size 1 is good only if it's an all-zero row. A subset of size 2, with rows i and p, is good if their combined column sums are at most 1. This is equivalent to (mask(row_i) & mask(row_p)) == 0.

It can be proven that if a good subset of any size k exists, then a good subset of size 1 or 2 must also exist. Therefore, we only need to check for these two simple cases.

The algorithm first iterates through the grid to find an all-zero row. If found, we are done. If not, we use a hash map to store the unique row patterns (as bitmasks) and their first-seen row indices. Since n <= 5, there are at most 2^5 = 32 unique masks. After populating the map, we check every pair of unique masks. If we find a pair whose bitwise AND is zero, we have found a good subset of size 2.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.Collections;4import java.util.HashMap;5import java.util.List;6import java.util.Map;7 8class Solution {9    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {10        int m = grid.length;11        int n = grid[0].length;12        // Map to store a representative index for each mask found13        Map<Integer, Integer> maskToIndex = new HashMap<>();14 15        for (int i = 0; i < m; i++) {16            int currentMask = 0;17            for (int j = 0; j < n; j++) {18                currentMask |= grid[i][j] << j;19            }20 21            // Case 1: Good subset of size 122            if (currentMask == 0) {23                return Arrays.asList(i);24            }25 26            maskToIndex.put(currentMask, i);27        }28 29        // Case 2: Good subset of size 230        for (int mask1 : maskToIndex.keySet()) {31            for (int mask2 : maskToIndex.keySet()) {32                if ((mask1 & mask2) == 0) {33                    int index1 = maskToIndex.get(mask1);34                    int index2 = maskToIndex.get(mask2);35                    // The problem asks for any good subset, so we can return the first one we find.36                    // Sorting is required for the output format.37                    return index1 < index2 ? Arrays.asList(index1, index2) : Arrays.asList(index2, index1);38                }39            }40        }41 42        return new ArrayList<>(); // No good subset found43    }44}