73. Set Matrix Zeroes

How to solve Set Matrix Zeroes (LeetCode 73): the approach in brief

The problem

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

Pattern

Set Matrix Zeroes is a Array/Matrix Manipulation Patterns problem, in the Set Matrix Zeroes (In-place Marking) subpattern. The pattern covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort

Learn the in-place marking technique to set entire rows and columns to zero efficiently without extra space.

Approach outline

1. If any cell of the matrix has a zero we can record its row and column number using additional memory. But if you don't want to use extra memory then you can manipulate the array instead. i.e. simulating exactly what the question says.
2. Setting cell values to zero on the fly while iterating might lead to discrepancies. What if you use some other integer value as your marker? There is still a better approach for this problem with O(1) space.
3. We could have used 2 sets to keep a record of rows/columns which need to be set to zero. But for an O(1) space solution, you can use one of the rows and and one of the columns to keep track of this information.

Complexity

The reference solution runs in O(m * n) time and O(1) space.

Asked at

Set Matrix Zeroes has been reported in interviews at Facebook, Microsoft, Oracle, Amazon, Expedia, Bloomberg, Goldman Sachs, Apple.