Zero Out Rows and Columns

You're at your Adobe onsite and the interviewer slides a matrix across the table. "If any cell is zero," they say, "I want the entire row and column set to zero. And do it in place." Your first instinct might be to grab a couple of boolean arrays and track which rows and columns to wipe. That works, but the follow-up is always the same: "Can you do it without extra space?" This problem tests your ability to think about the matrix itself as storage, and it shows up regularly at companies like Adobe, Apple, Microsoft, and Uber.

TL;DR

Scan the matrix for zeros. Instead of allocating separate arrays to remember which rows and columns need zeroing, use the first row and first column of the matrix as marker storage. Two boolean flags preserve whether the first row and column originally contained zeros. Mark, zero, then clean up the first row and column last. This runs in O(m * n) time and O(1) space.

The Problem

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Here is the first example. The zero at position (1,1) causes row 1 and column 1 to be zeroed out:

Input:

Output:

And a larger example with two zeros at (0,0) and (0,3):

Input:

Output:

Notice how the two zeros in the first row cause columns 0 and 3 to be fully zeroed. The entire first row is also zeroed because it contains the original zeros.

Why In-Place Matters

The straightforward approach allocates two boolean arrays: one of size m to track which rows contain zeros, and one of size n to track which columns contain zeros. That costs O(m + n) extra space.

In an interview, the follow-up question is almost always: "Can you bring the space down to O(1)?" The core idea is to realize the matrix already has spare storage you can repurpose. The first row can record which columns need zeroing, and the first column can record which rows need zeroing. The only complication is that the first row and column have their own original data, so you need two boolean variables to track whether those should be zeroed as well.

Algorithm Walkthrough

The algorithm breaks into four distinct phases:

For the 3x3 example [[1,1,1],[1,0,1],[1,1,1]], here is each phase in detail.

Phase 1: Record first row and column state

Before touching anything, scan the first column top to bottom and the first row left to right. If either contains a zero, set the corresponding flag (firstColZero or firstRowZero) to true.

For our 3x3 example, the first row is [1, 1, 1] and the first column is [1, 1, 1]. Neither contains a zero, so both flags stay false.

Phase 2: Mark zeros using the first row and column

Iterate over the interior of the matrix (rows 1 through m-1, columns 1 through n-1). Whenever you find a zero at matrix[i][j], set matrix[i][0] = 0 and matrix[0][j] = 0. This "marks" that row i and column j need to be zeroed.

For our example, the zero at (1,1) causes matrix[1][0] and matrix[0][1] to be set to zero:

The green cells along the top and left edges are the marker storage. The purple cells at (1,0) and (0,1) are the newly written markers. The orange cell at (1,1) is the original zero.

Phase 3: Zero out cells based on markers

Iterate over the interior again. For each cell (i, j), if matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0. This propagates the zero markers into actual zeros across the affected rows and columns.

Phase 4: Handle first row and column

If firstRowZero is true, zero out every cell in row 0. If firstColZero is true, zero out every cell in column 0. This step must come last because the markers stored in the first row and column were still needed during Phase 3.

For our example, both flags are false, so the first row and column keep their (now-marked) values. The final result is [[1,0,1],[0,0,0],[1,0,1]].

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int[][] setZeroes(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
      return matrix;
    }

    int m = matrix.length;
    int n = matrix[0].length;
    boolean firstRowZero = false;
    boolean firstColZero = false;

    // Phase 1: Check if the first column contains any zero
    for (int i = 0; i < m; i++) {
      if (matrix[i][0] == 0) {
        firstColZero = true;
        break;
      }
    }

    // Phase 1: Check if the first row contains any zero
    for (int j = 0; j < n; j++) {
      if (matrix[0][j] == 0) {
        firstRowZero = true;
        break;
      }
    }

    // Phase 2: Use first row and column as markers
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        if (matrix[i][j] == 0) {
          matrix[i][0] = 0;
          matrix[0][j] = 0;
        }
      }
    }

    // Phase 3: Zero out cells based on markers
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
          matrix[i][j] = 0;
        }
      }
    }

    // Phase 4: Handle first row
    if (firstRowZero) {
      for (int j = 0; j < n; j++) {
        matrix[0][j] = 0;
      }
    }

    // Phase 4: Handle first column
    if (firstColZero) {
      for (int i = 0; i < m; i++) {
        matrix[i][0] = 0;
      }
    }

    return matrix;
  }
}

Tracing Through the Second Example

For [[0,1,2,0],[3,4,5,2],[1,3,1,5]]:

Phase 1: The first column has a zero at (0,0), so firstColZero = true. The first row has zeros at (0,0) and (0,3), so firstRowZero = true.

Phase 2: No interior cell (rows 1-2, columns 1-2) is zero, so no markers are written.

Phase 3: No interior markers exist, so interior cells stay unchanged.

Phase 4: firstRowZero is true, so row 0 becomes [0, 0, 0, 0]. firstColZero is true, so column 0 becomes [0, 0, 0].

Result: [[0,0,0,0],[0,4,5,2],[0,3,1,5]].

Wait, that does not match the expected output [[0,0,0,0],[0,4,5,0],[0,3,1,0]]. The issue is that column 3 also needs to be zeroed because of the original zero at (0,3). Since (0,3) sits in the first row (our marker row), it actually marks column 3 as needing zeroing. During Phase 3, any cell where matrix[0][j] == 0 gets zeroed, and matrix[0][3] is already 0 from the original input. So cells (1,3) and (2,3) do get zeroed to produce the correct result.

The full trace confirms: matrix[0][3] is already 0, which means the Phase 3 loop sets matrix[1][3] = 0 and matrix[2][3] = 0. The final output is [[0,0,0,0],[0,4,5,0],[0,3,1,0]].

Complexity Analysis

Time Complexity: O(m * n)

The algorithm makes a fixed number of passes over the matrix. Each of the four phases visits at most m * n cells with constant work per cell. The total work is proportional to the size of the matrix.

Space Complexity: O(1)

Beyond the input matrix itself, the algorithm uses only two boolean variables (firstRowZero and firstColZero). All marker information is stored directly in the matrix's first row and column.

Comparison With Other Approaches

The in-place approach is what interviewers expect when they ask for a follow-up optimization.

Common Pitfalls

1. Zeroing the first row/column too early. If you zero the first row before processing the interior, every column gets falsely marked. Always handle the first row and column last.

2. Forgetting the boolean flags. Without firstRowZero and firstColZero, you cannot tell whether zeros in the first row/column are original or were written as markers.

3. Starting the interior scan at (0,0) instead of (1,1). The marking pass must skip the first row and column to avoid corrupting marker storage.

4. Modifying the matrix during the scan. In the brute-force approach, setting a cell to zero while scanning can trigger cascading false zeros. The two-phase approach (mark then zero) prevents this.

Interview Tips

When this problem comes up:

• Start by describing the O(m + n) space approach with two boolean arrays. It is correct and easy to explain.
• Then transition to the O(1) optimization: "We can use the first row and column as those arrays."
• Draw the four phases on the whiteboard. Interviewers appreciate a structured walkthrough.
• Emphasize the ordering constraint: interior zeroing must happen before first row/column zeroing.
• Test with edge cases: all zeros, no zeros, single row, single column, zeros only in the first row or column.

Key Takeaways

• The in-place marker technique repurposes existing matrix storage (first row and column) to record which rows and columns need zeroing, eliminating the need for O(m + n) auxiliary arrays.
• Two boolean flags are necessary to preserve the original state of the first row and column before they get overwritten during the marking phase.
• Phase ordering is critical: scan first row/column, mark interior, zero interior, then handle first row/column last. Reversing the last two steps corrupts the markers.
• This pattern of "use the data structure itself as scratch space" appears in several matrix problems, including Rotate Image and Game of Life.
• Test with at least four cases: the basic 3x3 example, the example with multiple zeros, an all-zero matrix, and a matrix with no zeros.

Related Problems

Once you are comfortable with this problem, try these:

• Rotate Image - another in-place matrix manipulation problem using the transpose-and-reverse approach
• Spiral Matrix - matrix traversal with boundary tracking
• Game of Life - in-place state transitions where neighbor reads and writes must not interfere
• Search a 2D Matrix - binary search on a row/column sorted matrix

Practice builds fluency. This problem and hundreds of others are available on Firecode, where you can drill matrix problems with spaced repetition until the patterns become second nature.

Solutions in Other Languages

Python

class Solution:
    def set_zeroes(self, matrix):
        if not matrix or not matrix[0]:
            return matrix

        m, n = len(matrix), len(matrix[0])
        first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
        first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))

        # Mark zeros using first row and column
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # Zero out rows based on markers
        for i in range(1, m):
            if matrix[i][0] == 0:
                for j in range(1, n):
                    matrix[i][j] = 0

        # Zero out columns based on markers
        for j in range(1, n):
            if matrix[0][j] == 0:
                for i in range(1, m):
                    matrix[i][j] = 0

        # Handle first row and column
        if first_row_has_zero:
            for j in range(n):
                matrix[0][j] = 0

        if first_col_has_zero:
            for i in range(m):
                matrix[i][0] = 0

        return matrix

JavaScript

class Solution {
  setZeroes(matrix) {
    if (!matrix.length || !matrix[0].length) {
      return matrix;
    }

    const m = matrix.length;
    const n = matrix[0].length;
    let firstRowHasZero = false;
    let firstColHasZero = false;

    for (let i = 0; i < m; i++) {
      if (matrix[i][0] === 0) {
        firstColHasZero = true;
        break;
      }
    }

    for (let j = 0; j < n; j++) {
      if (matrix[0][j] === 0) {
        firstRowHasZero = true;
        break;
      }
    }

    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 (firstRowHasZero) {
      for (let j = 0; j < n; j++) {
        matrix[0][j] = 0;
      }
    }

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

    return matrix;
  }
}

TypeScript

class Solution {
  setZeroes(matrix: number[][]): number[][] {
    const m = matrix.length;
    const n = matrix[0].length;
    let firstRowHasZero = false;
    let firstColHasZero = false;

    for (let i = 0; i < m; i++) {
      if (matrix[i][0] === 0) {
        firstColHasZero = true;
        break;
      }
    }

    for (let j = 0; j < n; j++) {
      if (matrix[0][j] === 0) {
        firstRowHasZero = true;
        break;
      }
    }

    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 (firstRowHasZero) {
      for (let j = 0; j < n; j++) {
        matrix[0][j] = 0;
      }
    }

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

    return matrix;
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<std::vector<int>> setZeroes(std::vector<std::vector<int>> &matrix) {
    if (matrix.empty()) return matrix;

    int m = matrix.size();
    int n = matrix[0].size();
    bool firstRowZero = false;
    bool firstColZero = false;

    for (int i = 0; i < m; ++i) {
      if (matrix[i][0] == 0) {
        firstColZero = true;
        break;
      }
    }

    for (int j = 0; j < n; ++j) {
      if (matrix[0][j] == 0) {
        firstRowZero = true;
        break;
      }
    }

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

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

    if (firstRowZero) {
      for (int j = 0; j < n; ++j) {
        matrix[0][j] = 0;
      }
    }

    if (firstColZero) {
      for (int i = 0; i < m; ++i) {
        matrix[i][0] = 0;
      }
    }

    return matrix;
  }
};

Go

func setZeroes(matrix [][]int) [][]int {
    if len(matrix) == 0 {
        return matrix
    }

    m, n := len(matrix), len(matrix[0])
    firstRowZero := false
    firstColZero := false

    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 {
            firstColZero = true
            break
        }
    }

    for j := 0; j < n; j++ {
        if matrix[0][j] == 0 {
            firstRowZero = true
            break
        }
    }

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

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

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

    if firstRowZero {
        for j := 0; j < n; j++ {
            matrix[0][j] = 0
        }
    }

    if firstColZero {
        for i := 0; i < m; i++ {
            matrix[i][0] = 0
        }
    }

    return matrix
}

Scala

class Solution {
  def setZeroes(matrix: Array[Array[Int]]): Array[Array[Int]] = {
    if (matrix.isEmpty || matrix.head.isEmpty) return matrix

    val m = matrix.length
    val n = matrix.head.length
    var firstRowHasZero = false
    var firstColHasZero = false

    for (j <- 0 until n) {
      if (matrix(0)(j) == 0) firstRowHasZero = true
    }

    for (i <- 0 until m) {
      if (matrix(i)(0) == 0) firstColHasZero = true
    }

    for (i <- 1 until m) {
      for (j <- 1 until n) {
        if (matrix(i)(j) == 0) {
          matrix(i)(0) = 0
          matrix(0)(j) = 0
        }
      }
    }

    for (i <- 1 until m) {
      for (j <- 1 until n) {
        if (matrix(i)(0) == 0 || matrix(0)(j) == 0) {
          matrix(i)(j) = 0
        }
      }
    }

    if (firstRowHasZero) {
      for (j <- 0 until n) matrix(0)(j) = 0
    }

    if (firstColHasZero) {
      for (i <- 0 until m) matrix(i)(0) = 0
    }

    matrix
  }
}

Kotlin

class Solution {
    fun setZeroes(matrix: Array<IntArray>): Array<IntArray> {
        if (matrix.isEmpty() || matrix[0].isEmpty()) {
            return matrix
        }

        val m = matrix.size
        val n = matrix[0].size
        var firstRowZero = false
        var firstColZero = false

        for (i in 0 until m) {
            if (matrix[i][0] == 0) {
                firstColZero = true
                break
            }
        }

        for (j in 0 until n) {
            if (matrix[0][j] == 0) {
                firstRowZero = true
                break
            }
        }

        for (i in 1 until m) {
            for (j in 1 until n) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                }
            }
        }

        for (i in 1 until m) {
            for (j in 1 until n) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0
                }
            }
        }

        if (firstRowZero) {
            for (j in 0 until n) matrix[0][j] = 0
        }

        if (firstColZero) {
            for (i in 0 until m) matrix[i][0] = 0
        }

        return matrix
    }
}

Rust

impl Solution {
    pub fn set_zeroes(mut matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        if matrix.is_empty() || matrix[0].is_empty() {
            return matrix;
        }

        let m = matrix.len();
        let n = matrix[0].len();
        let mut first_row_zero = false;
        let mut first_col_zero = false;

        for i in 0..m {
            if matrix[i][0] == 0 {
                first_col_zero = true;
                break;
            }
        }

        for j in 0..n {
            if matrix[0][j] == 0 {
                first_row_zero = true;
                break;
            }
        }

        for i in 1..m {
            for j in 1..n {
                if matrix[i][j] == 0 {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for i in 1..m {
            for j in 1..n {
                if matrix[i][0] == 0 || matrix[0][j] == 0 {
                    matrix[i][j] = 0;
                }
            }
        }

        if first_row_zero {
            for j in 0..n {
                matrix[0][j] = 0;
            }
        }

        if first_col_zero {
            for i in 0..m {
                matrix[i][0] = 0;
            }
        }

        matrix
    }
}

Swift

class Solution {
    func setZeroes(_ matrix: [[Int]]) -> [[Int]] {
        var matrix = matrix
        if matrix.isEmpty || matrix[0].isEmpty {
            return matrix
        }

        let m = matrix.count
        let n = matrix[0].count
        var firstRowZero = false
        var firstColZero = false

        for i in 0..<m {
            if matrix[i][0] == 0 {
                firstColZero = true
                break
            }
        }

        for j in 0..<n {
            if matrix[0][j] == 0 {
                firstRowZero = true
                break
            }
        }

        for i in 1..<m {
            for j in 1..<n {
                if matrix[i][j] == 0 {
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                }
            }
        }

        for i in 1..<m {
            for j in 1..<n {
                if matrix[i][0] == 0 || matrix[0][j] == 0 {
                    matrix[i][j] = 0
                }
            }
        }

        if firstRowZero {
            for j in 0..<n {
                matrix[0][j] = 0
            }
        }

        if firstColZero {
            for i in 0..<m {
                matrix[i][0] = 0
            }
        }

        return matrix
    }
}

Ruby

class Solution
  def set_zeroes(matrix)
    return matrix if matrix.nil? || matrix.empty? || matrix[0].empty?

    m = matrix.length
    n = matrix[0].length
    first_row_zero = false
    first_col_zero = false

    (0...m).each do |i|
      if matrix[i][0] == 0
        first_col_zero = true
        break
      end
    end

    (0...n).each do |j|
      if matrix[0][j] == 0
        first_row_zero = true
        break
      end
    end

    (1...m).each do |i|
      (1...n).each do |j|
        if matrix[i][j] == 0
          matrix[i][0] = 0
          matrix[0][j] = 0
        end
      end
    end

    (1...m).each do |i|
      (1...n).each do |j|
        if matrix[i][0] == 0 || matrix[0][j] == 0
          matrix[i][j] = 0
        end
      end
    end

    if first_row_zero
      (0...n).each { |j| matrix[0][j] = 0 }
    end

    if first_col_zero
      (0...m).each { |i| matrix[i][0] = 0 }
    end

    matrix
  end
end

Dart

class Solution {
  List<List<int>> setZeroes(List<List<int>> matrix) {
    if (matrix.isEmpty || matrix[0].isEmpty) {
      return matrix;
    }

    int m = matrix.length;
    int n = matrix[0].length;
    bool firstRowZero = false;
    bool firstColZero = false;

    for (int i = 0; i < m; i++) {
      if (matrix[i][0] == 0) {
        firstColZero = true;
        break;
      }
    }

    for (int j = 0; j < n; j++) {
      if (matrix[0][j] == 0) {
        firstRowZero = true;
        break;
      }
    }

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

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

    if (firstRowZero) {
      for (int j = 0; j < n; j++) {
        matrix[0][j] = 0;
      }
    }

    if (firstColZero) {
      for (int i = 0; i < m; i++) {
        matrix[i][0] = 0;
      }
    }

    return matrix;
  }
}

PHP

class Solution {
    public function setZeroes(array $matrix): array {
        if (empty($matrix) || empty($matrix[0])) {
            return $matrix;
        }

        $m = count($matrix);
        $n = count($matrix[0]);
        $firstRowZero = false;
        $firstColZero = false;

        for ($i = 0; $i < $m; $i++) {
            if ($matrix[$i][0] === 0) {
                $firstColZero = true;
                break;
            }
        }

        for ($j = 0; $j < $n; $j++) {
            if ($matrix[0][$j] === 0) {
                $firstRowZero = true;
                break;
            }
        }

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

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

        if ($firstRowZero) {
            for ($j = 0; $j < $n; $j++) {
                $matrix[0][$j] = 0;
            }
        }

        if ($firstColZero) {
            for ($i = 0; $i < $m; $i++) {
                $matrix[$i][0] = 0;
            }
        }

        return $matrix;
    }
}

C#

public class Solution {
    public int[][] setZeroes(int[][] matrix) {
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
            return matrix;
        }

        int m = matrix.Length;
        int n = matrix[0].Length;
        bool firstRowZero = false;
        bool firstColZero = false;

        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

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

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

        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }

        return matrix;
    }
}