Tap here to switch tabs
Problem
Submissions

Problem: Find a Good Subset of the Matrix

Find a Good Subset of the Matrix asks you to choose a nonempty set of row indices where each column has at most the floor of half the selected rows as ones, returning sorted indices or an empty array if none exists.

Statement

Given a 00 indexed m×nm \times n binary matrix grid.

A non empty subset of rows is considered good if the sum of elements in each column across the chosen subset is at most half of the size of the subset. That is, if the subset contains kk rows, the sum of elements in each column within those rows must not exceed ⌊k2⌋\lfloor \frac{k}{2} \rfloor.

Return an array containing the indices of the rows belonging to any good subset, sorted in ascending order. If there are multiple valid good subsets, return any of them. If no such subset exists, return an empty array.

Constraints:

  • m ==== grid.length

  • n ==== grid[i].length

  • 1≤1 \leq m ≤104\leq 10^4

  • 1≤1 \leq n ≤5\leq 5

  • grid[i][j] is either 00 or 11.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find a Good Subset of the Matrix

Find a Good Subset of the Matrix asks you to choose a nonempty set of row indices where each column has at most the floor of half the selected rows as ones, returning sorted indices or an empty array if none exists.

Statement

Given a 00 indexed m×nm \times n binary matrix grid.

A non empty subset of rows is considered good if the sum of elements in each column across the chosen subset is at most half of the size of the subset. That is, if the subset contains kk rows, the sum of elements in each column within those rows must not exceed ⌊k2⌋\lfloor \frac{k}{2} \rfloor.

Return an array containing the indices of the rows belonging to any good subset, sorted in ascending order. If there are multiple valid good subsets, return any of them. If no such subset exists, return an empty array.

Constraints:

  • m ==== grid.length

  • n ==== grid[i].length

  • 1≤1 \leq m ≤104\leq 10^4

  • 1≤1 \leq n ≤5\leq 5

  • grid[i][j] is either 00 or 11.