Set Matrix Zeroes Easy 0 attempts
LeetCode ↗

Set Matrix Zeroes

Easy ArrayTwo Pointers LeetCode

Given an m x n integer matrix, if any element is 0, set its entire row and entire column to 0. The modification must be done in-place.

A straightforward approach uses O(m + n) extra space. The challenge is doing it in O(1) extra space.

Examples

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

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]
]

Constraints

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1
Sample Input
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Sample Output
[[1,0,1],[0,0,0],[1,0,1]]
Constraints
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1
Test Cases
Case 1
Args: [[[1,1,1],[1,0,1],[1,1,1]]] Expected: [[1,0,1],[0,0,0],[1,0,1]]
Topics
ArrayTwo Pointers

Use the first row and first column as markers. Scan the matrix — when a zero is found, mark the corresponding first-row and first-column cell as zero. Then do a second pass to zero out marked rows and columns. Handle the first row and column separately using a dedicated flag to avoid overwriting markers prematurely.

function setZeroes(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  let firstRowZero = false;
  let firstColZero = false;

  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) firstColZero = true;
  }
  for (let j = 0; j < n; j++) {
    if (matrix[0][j] === 0) firstRowZero = true;
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
  }

  if (firstRowZero) {
    for (let j = 0; j < n; j++) matrix[0][j] = 0;
  }
  if (firstColZero) {
    for (let i = 0; i < m; i++) matrix[i][0] = 0;
  }
}

Time: O(m * n) — two full passes over the matrix. Space: O(1) — markers stored in the matrix itself.

Saved in this browser only. Private to you.

JavaScript