1+ /*
2+ Given a 2d matrix if an element is 0, set it's entire row and column to 0 as
3+ well.
4+ Ex. matrix = [[ 1, 1, 1], [[ 1, 0, 1],
5+ [ 1, 0, 1], -> [ 0, 0, 0],
6+ [ 1, 1, 1]] [ 1, 0, 1]]
7+
8+ An identical result matrix can be initialised and then updated according to
9+ the zeros values in the original matrix. However, this would take O(m*n)
10+ space, which can be improved.
11+
12+ By doing the updations in the same matrix, space complexity becomes O(1). We
13+ reserve the top most row as marker, they will signify whether the
14+ corresponding column has a zero or not. Similarly the first column, will do
15+ the same for the rows.
16+
17+ An additional variable is needed as the m[0][0] is common in both the first
18+ row and first column.
19+
20+ Time: O(m*n) where m, n are the matrix dimensions
21+ Space: O(1)
22+ */
23+
24+ void setZeroes (int * * matrix ,int matrixSize ,int * matrixColSize ){
25+ int ROW = matrixSize ;
26+ int COL = * matrixColSize ;
27+ bool rowZero = false;
28+
29+ for (int r = 0 ;r < ROW ;++ r ) {
30+ for (int c = 0 ;c < COL ;++ c ) {
31+ if (matrix [r ][c ]== 0 ) {
32+ matrix [0 ][c ]= 0 ;
33+ if (r > 0 )
34+ matrix [r ][0 ]= 0 ;
35+ else
36+ rowZero = true;
37+ }
38+ }
39+ }
40+
41+ for (int r = 1 ;r < ROW ;++ r ) {
42+ for (int c = 1 ;c < COL ;++ c ) {
43+ if (matrix [0 ][c ]== 0 || matrix [r ][0 ]== 0 )
44+ matrix [r ][c ]= 0 ;
45+ }
46+ }
47+
48+ // Set first column as zeros if matrix[0][0] is set
49+ if (matrix [0 ][0 ]== 0 ) {
50+ for (int r = 0 ;r < ROW ;++ r ) {
51+ matrix [r ][0 ]= 0 ;
52+ }
53+ }
54+
55+ // Set first row as zeros if rowZero is true
56+ if (rowZero ) {
57+ for (int c = 0 ;c < COL ;++ c ) {
58+ matrix [0 ][c ]= 0 ;
59+ }
60+ }
61+ }