← All coding problems
Set Matrix Zeroes
mediumArrays & Hashing+20 XPTime limit 2s
Whenever a cell of the matrix is 0, set its entire row and entire column to 0. (Zeros created by this process don't spread further — only the original zeros count.)
Input:
- line 1:
r c - next
rlines:cintegers each
Output: the resulting matrix, one row per line.
Constraints: 1 ≤ r, c ≤ 300, −10⁹ ≤ value ≤ 10⁹.
Challenge: first record which rows and columns contain a zero, then rewrite. Then try O(1) extra memory by using the first row and column as your markers.
Sample input 1
3 3 1 1 1 1 0 1 1 1 1
Sample output 1
1 0 1 0 0 0 1 0 1
Sample input 2
3 4 0 1 2 0 3 4 5 2 1 3 1 5
Sample output 2
0 0 0 0 0 4 5 0 0 3 1 0
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).