Set Matrix Zeroes
Module 15 · Matrix / 2D Traversal
Problem
Given an m × n matrix, if any cell is 0, set its entire row and
entire column to 0. Do it in place. (LeetCode 73.)
Examples
Example 1
matrix = [[1,1,1],[1,0,1],[1,1,1]]Output[[1,0,1],[0,0,0],[1,0,1]]Example 2
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
1 ≤ m, n ≤ 200, values in ±2³¹. The follow-up that makes this problem interesting: a simple solution uses O(m+n) extra space; can you do it with O(1) extra space? That follow-up is the whole lesson.
Attempt it first
Try the obvious thing first and watch it fail — that failure is the
teacher here. The naive move is: scan the grid, and whenever you see a
0, immediately zero out its row and column. Do it on the second
example above and trace carefully. Something goes wrong almost
immediately. Understand what goes wrong before reading on; it's the
observation the whole problem is built around.