If any element of a matrix is 0, set its entire row and column to 0 (do it based on the ORIGINAL zeros, not ones created during the pass).
The trap is mutating as you go, which spreads zeros incorrectly. First record which rows and columns contain a zero (in sets, or using the first row/column as markers for O(1) space), then zero them in a second pass. O(m * n) time.
public static void setZeroes(int[][] m) {
Set<Integer> rows = new HashSet<>(), cols = new HashSet<>();
for (int i = 0; i < m.length; i++)
for (int j = 0; j < m[0].length; j++)
if (m[i][j] == 0) { rows.add(i); cols.add(j); }
for (int i = 0; i < m.length; i++)
for (int j = 0; j < m[0].length; j++)
if (rows.contains(i) || cols.contains(j)) m[i][j] = 0;
}function setZeroes(m) {
const rows = new Set(), cols = new Set();
for (let i = 0; i < m.length; i++)
for (let j = 0; j < m[0].length; j++)
if (m[i][j] === 0) { rows.add(i); cols.add(j); }
for (let i = 0; i < m.length; i++)
for (let j = 0; j < m[0].length; j++)
if (rows.has(i) || cols.has(j)) m[i][j] = 0;
return m;
}def set_zeroes(m):
rows, cols = set(), set()
for i in range(len(m)):
for j in range(len(m[0])):
if m[i][j] == 0:
rows.add(i)
cols.add(j)
for i in range(len(m)):
for j in range(len(m[0])):
if i in rows or j in cols:
m[i][j] = 0
return mPropagating a flag across a row/column models spreadsheet recalculation and grid invalidation — with the classic "detect first, then apply" discipline.
A candidate zeros the row and column the moment they see a 0, and the whole matrix becomes 0. Fix?