Skip to main content

57. Set Matrix Zeroes

mediumAsked at Ola

Zero out the row and column of every zero in a matrix, in-place.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0s. Do it in-place; aim for O(1) extra space.

Constraints

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200

Examples

Example 1

Input
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output
[[1,0,1],[0,0,0],[1,0,1]]

Example 2

Input
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output
[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Approaches

1. Track row/col sets

Record rows and cols that contain a zero; zero them in a second pass.

Time
O(m*n)
Space
O(m+n)
const rows = new Set(), cols = new Set();
for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (matrix[i][j]===0){ rows.add(i); cols.add(j); }
for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (rows.has(i)||cols.has(j)) matrix[i][j]=0;

Tradeoff:

2. First row/col as markers

Use the matrix's own first row/col as the zero-flags; track first row/col separately and apply at the end.

Time
O(m*n)
Space
O(1)
function setZeroes(m) {
  const R = m.length, C = m[0].length;
  let r0 = false, c0 = false;
  for (let j = 0; j < C; j++) if (m[0][j] === 0) r0 = true;
  for (let i = 0; i < R; i++) if (m[i][0] === 0) c0 = true;
  for (let i = 1; i < R; i++) for (let j = 1; j < C; j++) if (m[i][j] === 0) { m[i][0] = 0; m[0][j] = 0; }
  for (let i = 1; i < R; i++) for (let j = 1; j < C; j++) if (m[i][0] === 0 || m[0][j] === 0) m[i][j] = 0;
  if (r0) for (let j = 0; j < C; j++) m[0][j] = 0;
  if (c0) for (let i = 0; i < R; i++) m[i][0] = 0;
}

Tradeoff:

Ola-specific tips

Ola interviewers like the in-place marker trick; tie it to compactly invalidating an entire row of cells when one driver in a zone goes offline.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Set Matrix Zeroes and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →