Pattern Recognition Drill

#119 — Set Matrix Zeroes

Medium Math & Geometry

The Problem

Given an m×n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

What approach would you use?

Think about it before scrolling down.

Key Signals

'In-place' with row/column zeroing → use first row and column as markers
'If element is 0' → need to remember which rows/columns without extra O(m+n) space

Matrix Traversal

Use first row/col as flags. Separate flag for row0/col0 themselves. Two passes. O(mn) time, O(1) space.

Alt: Hash Map

Track zero rows and columns in sets. O(m+n) space — simpler but not O(1).

Common Trap

Process the first row and column LAST, otherwise you corrupt the markers.

← #118