Set Matrix Zeroes

If a cell is 0, set its entire row and column to 0. Do it in place.

A way to picture it

You're a building inspector marking condemned floors and shafts. You can't knock them down the moment you spot a crack, or the rubble would look like new cracks. So you leave sticky notes on the ground floor and the first shaft, then demolish everything at the end.

How to approach it

Use the first row and first column as markers for which columns and rows to zero. Remember separately whether the first row and first column themselves started with a 0.

Example

Input: {"matrix":[[1,1,1],[1,0,1],[1,1,1]]}. Output: [[1,0,1],[0,0,0],[1,0,1]].

Complexity: O(m · n) time and O(1) space. A few passes over the grid; the markers live inside it.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.