Skip to content

2732. Find a Good Subset of the Matrix 👍

  • Time: $O(32m) = O(m)$
  • Space: $O(2^n) = O(2^5) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
    final int MAX_BIT = 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 < MAX_BIT; ++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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def goodSubsetofBinaryMatrix(self, grid: list[list[int]]) -> list[int]:
    MAX_BIT = 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, MAX_BIT):
        if (mask & prevMask) == 0 and prevMask in maskToIndex:
          return [maskToIndex[prevMask], i]
      maskToIndex[mask] = i

    return []