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

Examples

Example 1:

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

Example 2:

Input:  [[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
  • Follow-up: Can you solve it with O(1) extra space?

Thinking Process

The naive approach (modify while scanning) corrupts the matrix – new zeros trigger more zeros than intended. We need to record which rows and columns to zero out first, then apply.

Three levels of space usage:

  1. O(m + n): Use separate sets/arrays for row and column markers
  2. O(1): Use the matrix’s own first row and first column as markers
Grid traversal BFS/DFS flood from each cell

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Row/column traversal O(nm) O(1) Simulation, spiral
BFS/DFS on grid O(nm) O(nm) Islands, shortest path
Matrix as graph (this problem) O(nm) O(nm) 4/8-directional neighbors
Transpose / rotate O(nm) O(1) In-place rotation tricks

Solution

Scan for zeros, record their rows and columns, then zero out.

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

Solution Explanation

Approach: Matrix as graph (this problem)

Key idea: The naive approach (modify while scanning) corrupts the matrix – new zeros trigger more zeros than intended. We need to record which rows and columns to zero out first, then apply.

How the code works:

  1. O(m + n): Use separate sets/arrays for row and column markers
  2. O(1): Use the matrix’s own first row and first column as markers

Walkthrough — input [[1,1,1],[1,0,1],[1,1,1]], expected output [[1,0,1],[0,0,0],[1,0,1]]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Comparison

Approach Time Space Notes
Hash Sets O(m · n) O(m + n) Simple and clear
In-Place Markers O(m · n) O(1) Uses matrix itself; interview follow-up

Common Mistakes

  • Zeroing out row 0 / column 0 before processing the interior (destroys marker data)
  • Modifying the matrix during the scan pass (new zeros cascade incorrectly)
  • Forgetting to separately handle row 0 and column 0 (they overlap at matrix[0][0])

Key Takeaways

  • “Mark then apply” is the core pattern – never modify and read from the same data simultaneously
  • Using the matrix’s own borders as storage is a classic O(1) space trick
  • The order of operations is critical: scan → mark → apply interior → apply borders

References

Template Reference