Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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.
Example 1:
Input: grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]] Output: [0,1] Explanation: We can choose the 0th and 1st rows to create a good subset of rows. The length of the chosen subset is 2. - The sum of the 0th column is 0 + 0 = 0, which is at most half of the length of the subset. - The sum of the 1st column is 1 + 0 = 1, which is at most half of the length of the subset. - The sum of the 2nd column is 1 + 0 = 1, which is at most half of the length of the subset. - The sum of the 3rd column is 0 + 1 = 1, which is at most half of the length of the subset.
Example 2:
Input: grid = [[0]] Output: [0] Explanation: We can choose the 0th row to create a good subset of rows. The length of the chosen subset is 1. - The sum of the 0th column is 0, which is at most half of the length of the subset.
Example 3:
Input: grid = [[1,1,1],[1,1,1]] Output: [] Explanation: It is impossible to choose any subset of rows to create a good subset.
Constraints:
m == grid.lengthn == grid[i].length1 <= m <= 1041 <= n <= 5grid[i][j] is either 0 or 1.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Bit Manipulation
[[0,1,1,0],[0,0,0,1],[1,1,1,1]]
[[0]]
[[1,1,1],[1,1,1]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2732: Find a Good Subset of the Matrix
class Solution {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
Map<Integer, Integer> g = new HashMap<>();
for (int i = 0; i < grid.length; ++i) {
int mask = 0;
for (int j = 0; j < grid[0].length; ++j) {
mask |= grid[i][j] << j;
}
if (mask == 0) {
return List.of(i);
}
g.put(mask, i);
}
for (var e1 : g.entrySet()) {
for (var e2 : g.entrySet()) {
if ((e1.getKey() & e2.getKey()) == 0) {
int i = e1.getValue(), j = e2.getValue();
return List.of(Math.min(i, j), Math.max(i, j));
}
}
}
return List.of();
}
}
// Accepted solution for LeetCode #2732: Find a Good Subset of the Matrix
func goodSubsetofBinaryMatrix(grid [][]int) []int {
g := map[int]int{}
for i, row := range grid {
mask := 0
for j, x := range row {
mask |= x << j
}
if mask == 0 {
return []int{i}
}
g[mask] = i
}
for a, i := range g {
for b, j := range g {
if a&b == 0 {
return []int{min(i, j), max(i, j)}
}
}
}
return []int{}
}
# Accepted solution for LeetCode #2732: Find a Good Subset of the Matrix
class Solution:
def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
g = {}
for i, row in enumerate(grid):
mask = 0
for j, x in enumerate(row):
mask |= x << j
if mask == 0:
return [i]
g[mask] = i
for a, i in g.items():
for b, j in g.items():
if (a & b) == 0:
return sorted([i, j])
return []
// Accepted solution for LeetCode #2732: Find a Good Subset of the Matrix
use std::collections::HashMap;
impl Solution {
pub fn good_subsetof_binary_matrix(grid: Vec<Vec<i32>>) -> Vec<i32> {
let mut g: HashMap<i32, i32> = HashMap::new();
for (i, row) in grid.iter().enumerate() {
let mut mask = 0;
for (j, &x) in row.iter().enumerate() {
mask |= x << j;
}
if mask == 0 {
return vec![i as i32];
}
g.insert(mask, i as i32);
}
for (&a, &i) in g.iter() {
for (&b, &j) in g.iter() {
if (a & b) == 0 {
return vec![i.min(j), i.max(j)];
}
}
}
vec![]
}
}
// Accepted solution for LeetCode #2732: Find a Good Subset of the Matrix
function goodSubsetofBinaryMatrix(grid: number[][]): number[] {
const g: Map<number, number> = new Map();
const m = grid.length;
const n = grid[0].length;
for (let i = 0; i < m; ++i) {
let mask = 0;
for (let j = 0; j < n; ++j) {
mask |= grid[i][j] << j;
}
if (!mask) {
return [i];
}
g.set(mask, i);
}
for (const [a, i] of g.entries()) {
for (const [b, j] of g.entries()) {
if ((a & b) === 0) {
return [Math.min(i, j), Math.max(i, j)];
}
}
}
return [];
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.