2732. Find a Good Subset of the Matrix
Problem Explanation
You have a 2-dimensional m*n
binary matrix (grid
) indexed by 0 where m
is the number of rows and n
is the number of columns. You have to pick some rows (possibly none/all) from this matrix such that the sum of all chosen subset of rows should be at most half of the total number of rows you selected. More formally, if k
rows are selected, the sum of selected rows should be at most floor(k / 2).
You should return the indices of rows of this 'good' subset. These indices should be in ascending order. There can be multiple good subsets and you only need to return one. If no good subset exists, return an empty array.
Let's walk through an example;
Consider the following binary matrix:
0 1 1 1 0 1 0 1 0 1 1 1
Here we can choose the rows with the indices 0 and 2, which gives us the following subset:
0 1 1 0 1 0
The sum of all the elements in this subset is 3 which is less than or equal to the floor of half the number of rows (floor(2 / 2) = 1).
Solution Approach
The solution approach for this problem involves using a hash map (unordered_map
in C++) to map row mask to row index and a bitwise operation to get the mask from the row.
A helper method getMask
is used to calculate the row mask. The row mask of a row is the integer representation of the binary number which the row represents. For each row in the given grid, the row mask is calculated and checked if it's 0. If it is 0, return the current index because a row with all 0s is always a good subset.
If the mask is different from 0, iterate through the bit value of each column (from 1 to kMaxBit
) where kMaxBit
is the maximum bit representing the columns of the grid. If the bit of the row mask at the current column is 0 and the current bit is present in our hash map, return an array containing the index of the row saved in the hash map and the current index because these rows fulfill the condition of a good subset. If the current row mask is not present in the map, add it with its index.
Finally, if the program checks all rows and hasn't return, then there is no good subset present. It returns an empty array.
This solution is using Bits manipulation
, Hash Map
data structure and Iteration
pattern.
Solutions
C++ Solution
cpp
class Solution {
public:
vector<int> goodSubsetOfBinaryMatrix(vector<vector<int>>& grid) {
constexpr int kMaxBit = 32;
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) // Iterating through each bit
if ((mask & prevMask) == 0 && maskToIndex.count(prevMask)) // Checking if the bit of the row mask at the current column is 0 and the current bit is present in the hash map
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) // Calculating mask of the row
if (row[i] == 1)
mask |= 1 << i;
return mask;
}
};
Python Solution
python import collections K_MAX_BIT = 32 class Solution: def get_mask(self, row): mask = 0 for i in range(len(row)): if row[i] == 1: mask |= 1 << i return mask def goodSubsetOfBinaryMatrix(self, grid): mask_to_index = {} for i in range(len(grid)): mask = self.get_mask(grid[i]) if mask == 0: return [i] for prev_mask in range(1, K_MAX_BIT): if (mask & prev_mask) == 0 and prev_mask in mask_to_index: return [mask_to_index[prev_mask], i] mask_to_index[mask] = i return []
Java Solution
java class Solution { 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; } public int[] goodSubsetOfBinaryMatrix(int[][] grid) { final int K_MAX_BIT = 32; Map<Integer, Integer> maskToIndex = new HashMap<>(); for (int i = 0; i < grid.length; ++i) { int mask = getMask(grid[i]); if (mask == 0) return new int[]{i}; for (int prevMask = 1; prevMask < K_MAX_BIT; ++prevMask) if ((mask & prevMask) == 0 && maskToIndex.containsKey(prevMask)) return new int[] {maskToIndex.get(prevMask), i}; maskToIndex.put(mask, i); } return new int[]{}; } }
Please note that we need to implement other language solutions as well.
JavaScript Solution
javascript var goodSubsetOfBinaryMatrix = function(grid) { let maskToIndex = {}; const K_MAX_BIT = 32; const getMask = (row) => { let mask = 0; for (let i = 0; i < row.length; ++i) if (row[i] === 1) mask |= 1 << i; return mask; } for (let i = 0; i < grid.length; ++i) { let mask = getMask(grid[i]); if (mask === 0) return [i]; for (let prevMask = 1; prevMask < K_MAX_BIT; ++prevMask) if ((mask & prevMask) === 0 && prevMask in maskToIndex) return [maskToIndex[prevMask], i]; maskToIndex[mask] = i; } return []; };
With the above solutions implemented in different languages, we can solve the problem of good subset selection in a 2D binary matrix for different use-cases. Regardless of the language you choose, the core idea of the solution remains the same.
It is important to note that this problem makes extensive use of bitwise operators and hash maps, therefore understanding these concepts is crucial for solving similar problems. Also, the use of bitwise operators makes lookup operations faster and the algorithm more efficient, where the time complexity is O(N) where N is the size of the grid.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhat data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!