This is a problem from LeetCode from the latest biweekly contest.
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.
Constraints:
m == grid.length; n == grid[i].length; 1 <= m <= 10^4; 1 <= n <= 5; grid[i][j] is either 0 or 1.
Instead of finding any subset, I misread the problem to be : Find the maximum number of rows that can be selected to form a subset that meet the above condition.
I could not solve this harder version. I wonder if this version can be solved given the constraints. Any help / insight on this is appreciated.
The number of distinct rows is no more than $$$2^5$$$. If there exists a valid set then there exists a valid set with size at most $$$m$$$. So max size of a valid set is at most 5. Brute force through all of them in $$$(2^5)^5$$$. In my implementation, I have replaced 0s with 1s and 1s with -1s so my condition for a good set is that the sum of all columns must be non-negative.
https://leetcode.com/submissions/detail/968251377/
Can you please elaborate more.mainly on the brute force part how you are checking a valid set
Why is the max size of valid set is at most 5?
If we have the following grid, then max valid set size is 6 (picking all rows), right?
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 1 1 1 1
Yep you are right. The top comment mistakenly gave a solution for the original problem. By "max size of a valid set" I think they meant an upper bound to the minimum size.
Do you have a proof of why 5 is an upperbound?
You can actually show that 2 is an upper bound. To do this, we will show that:
[Existence of a valid subset] $$$\iff$$$ [There exists a pair of rows $$$(i, j)$$$ where $$$(i & j) = 0$$$]. Here, $$$i$$$ and $$$j$$$ are the numbers encoded in the set bits of the rows.
Backward direction: This is easy to see.
Forward direction: Suppose we have a valid subset with $$$k$$$ rows, where no row consists entirely of zeroes (otherwise we can simply take that row and be done):
Lemma: There exists a row in this subset with at least 3 zeroes.
Proof: We know that each column in the subset has at least $$$\lceil\frac{k}{2}\rceil$$$ zeroes. We know that there are 5 columns. So, there are at least $$$5\lceil\frac{k}{2}\rceil$$$ zeroes in total. Also, $$$5\lceil\frac{k}{2}\rceil > 2k$$$, which proves the statement.
Now, suppose we choose a row from our subset with at least 3 zeroes. There are 2 cases:
What does this mean? The original problem can be solved simply by finding any pair of rows with a bitwise-AND of zero. This is not too hard for $$$n = 5$$$, and for slightly bigger $$$n$$$ we can use SOS DP.
Thank you very much!
thank you so much for the proof. I tried searching on leetcode for proof, but wasn't able to find a good one. IDK how to even solve these in an actual contest. This problem was on hold for me for so many days cuz I was not able to find proof.
Interestingly, the original problem for $$$n \geq 6$$$ is also very hard.
I saw answer for this on Youtube, In that they said, if we have an observation we can see that we need to check for K = 0 && K = 1 and it will be enough and if it is not possible for K = 1 && K = 2, then it will be never possible for any other K.