Smallest Balanced Set of Rows

Hard

You are given a table table of zeros and ones whose rows are all distinct. Call a non-empty set of k rows *balanced* if, in every column, the chosen rows add up to at most ⌊k / 2⌋. Find a balanced set with the fewest rows and return the indices of its rows in increasing order. If there are several such sets, return the one whose index list is lexicographically smallest. If no balanced set exists at all, return an empty list. Hint: there are at most five columns. Think about whether a large balanced set can exist when no small one does.

Example 1

table=[[1, 1, 0], [1, 0, 1], [0, 1, 0], [0, 0, 1]] → [0, 3]

There is no all-zero row. Rows 0 and 1 share a 1 in column 0, but rows 0 and 3 share none: every column sums to at most 1 = ⌊2 / 2⌋. The pair (0, 3) is the first such pair in order.

Example 2

table=[[1, 0], [0, 0], [0, 1]] → [1]

Row 1 is all zeros, so the set made of that row alone is already balanced, and nothing is smaller.

Example 3

table=[[1, 1], [1, 0], [0, 1]] → [1, 2]

Rows 1 and 2 share no 1s, so the answer is [1, 2].

Constraints

1 ≤ len(table) ≤ 10⁴
1 ≤ len(table[i]) ≤ 5
table[i][j] is 0 or 1
All rows of table are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Hash Table Matrix