Set Matrix Zeroes

Given an R x C matrix, if an element is 0, set its entire row and column to 0 — in place, ideally using O(1) extra space instead of a second matrix to track which rows/columns to zero.

Example

Input:

Output:

Approach

The O(1)-space trick: use the matrix's own first row and first column as the "which rows/columns need zeroing" markers, instead of allocating separate boolean arrays. Since that overwrites two cells that matter for the first row/column's own zero status, save those two flags in two plain variables before touching anything. Scan the rest of the matrix marking grid[i][0]/grid[0][j] when grid[i][j] is 0, then scan again applying those marks, then finally zero the first row/column themselves based on the two saved flags.

Input format

Line 1: R C Next R lines: C space-separated integers

Print the resulting matrix, one row per line, space-separated.