2732. Find a Good Subset of the Matrix LeetCode Solution

In this guide, you will get 2732. Find a Good Subset of the Matrix LeetCode Solution with the best time and space complexity. The solution to Find a Good Subset of the Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find a Good Subset of the Matrix solution in C++
Find a Good Subset of the Matrix solution in Java
Find a Good Subset of the Matrix solution in Python
Additional Resources

2732. Find a Good Subset of the Matrix LeetCode Solution image

Problem Statement of Find a Good Subset of the Matrix

You are given a 0-indexed m x n binary matrix grid.
Let us call a non-empty subset of rows good if the sum of each column of the subset is at most half of the length of the subset.
More formally, if the length of the chosen subset of rows is k, then the sum of each column should be at most floor(k / 2).
Return an integer array that contains row indices of a good subset sorted in ascending order.
If there are multiple good subsets, you can return any of them. If there are no good subsets, return an empty array.
A subset of rows of the matrix grid is any matrix that can be obtained by deleting some (possibly none or all) rows from grid.

Example 1:

Input: grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
Output: [0,1]
Explanation: We can choose the 0th and 1st rows to create a good subset of rows.
The length of the chosen subset is 2.
– The sum of the 0th column is 0 + 0 = 0, which is at most half of the length of the subset.
– The sum of the 1st column is 1 + 0 = 1, which is at most half of the length of the subset.
– The sum of the 2nd column is 1 + 0 = 1, which is at most half of the length of the subset.
– The sum of the 3rd column is 0 + 1 = 1, which is at most half of the length of the subset.

Example 2:

Input: grid = [[0]]
Output: [0]
Explanation: We can choose the 0th row to create a good subset of rows.
The length of the chosen subset is 1.
– The sum of the 0th column is 0, which is at most half of the length of the subset.

Example 3:

Input: grid = [[1,1,1],[1,1,1]]
Output: []
Explanation: It is impossible to choose any subset of rows to create a good subset.

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 104
1 <= n <= 5
grid[i][j] is either 0 or 1.

Complexity Analysis

Time Complexity: O(32m) = O(m)
Space Complexity: O(2^n) = O(2^5) = O(1)

2732. Find a Good Subset of the Matrix LeetCode Solution in C++

class Solution {
 public:
  vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
    constexpr int kMaxBit = 30;
    unordered_map<int, int> maskToIndex;

    for (int i = 0; i < grid.size(); ++i) {
      const int mask = getMask(grid[i]);
      if (mask == 0)
        return {i};
      for (int prevMask = 1; prevMask < kMaxBit; ++prevMask)
        if ((mask & prevMask) == 0 && maskToIndex.contains(prevMask))
          return {maskToIndex[prevMask], i};
      maskToIndex[mask] = i;
    }

    return {};
  }

 private:
  int getMask(const vector<int>& row) {
    int mask = 0;
    for (int i = 0; i < row.size(); ++i)
      if (row[i] == 1)
        mask |= 1 << i;
    return mask;
  }
};
/* code provided by PROGIEZ */

2732. Find a Good Subset of the Matrix LeetCode Solution in Java

class Solution {
  public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
    final int kMaxBit = 30;
    Map<Integer, Integer> maskToIndex = new HashMap<>();

    for (int i = 0; i < grid.length; ++i) {
      final int mask = getMask(grid[i]);
      if (mask == 0)
        return List.of(i);
      for (int prevMask = 1; prevMask < kMaxBit; ++prevMask)
        if ((mask & prevMask) == 0 && maskToIndex.containsKey(prevMask))
          return List.of(maskToIndex.get(prevMask), i);
      maskToIndex.put(mask, i);
    }

    return new ArrayList<>();
  }

  private int getMask(int[] row) {
    int mask = 0;
    for (int i = 0; i < row.length; ++i)
      if (row[i] == 1)
        mask |= 1 << i;
    return mask;
  }
}
// code provided by PROGIEZ

2732. Find a Good Subset of the Matrix LeetCode Solution in Python

class Solution:
  def goodSubsetofBinaryMatrix(self, grid: list[list[int]]) -> list[int]:
    kMaxBit = 30
    maskToIndex = {}

    def getMask(row: list[int]) -> int:
      mask = 0
      for i, num in enumerate(row):
        if num == 1:
          mask |= 1 << i
      return mask

    for i, row in enumerate(grid):
      mask = getMask(row)
      if mask == 0:
        return [i]
      for prevMask in range(1, kMaxBit):
        if (mask & prevMask) == 0 and prevMask in maskToIndex:
          return [maskToIndex[prevMask], i]
      maskToIndex[mask] = i

    return []
 # code by PROGIEZ