## Introduction

Another interview question about matrices. Matrices have been of great interest in programming and Linear Algebra and a matter of study for most of the programmers. The problem statement follows:

“Given a matrix A of size M * N where M is the number of rows and N is the number of columns and each of its cell A[i][j] is populated with either zero or one. Transform the matrix such that if there exists a cell A[i][j] = 0 then the row i and column j is zero in the resultant matrix”.

You must not use extra space and try to solve it in lowest possible running time.

## Understanding the problem and approach to solve it

Given below an input matrix A, notice the cells with zeroes. The resultant matrix A_{Transform} contains all those rows and columns as zeroes.

The idea behind the solution is to pre process the matrix once and gather some information about the rows and columns which should be marked as zeroes. Then pass through the matrix once again and mark the rows and columns zeroes.

##### First Approach – Using extra space.

When we are free to use extra space, we will use two linked lists or arrays of maximum size M and N, say X_{M} and Y_{N}. Then we traverse through the matrix and for each cell A[i][j] if it is zero them we store 1 at the i^{th} index of X_{M} and to the j^{th} index of Y_{N}.

Once we are done with this pre processing, we just need to traverse through X_{M} and Y_{N} one at a time and mark the corresponding rows and columns in the matrix as zero.

##### Second Approach – Not using extra space

As we understood that we need to collect some meta data while pre processing and later use that meta data to mark rows and columns as zeroes. Instead of using a different array of linked list, we can try to manipulate the matrix and store the meta data there it self.

Let us traverse through the matrix in pre processing and for a cell A[i][j] equal to zero we assign a value 2 to the cells A[i][0] to A[i][N]. Similarly we assign a value 2 for cells A[0][j] to A[M][j].

Next time iterate through the matrix and change each cell A[i][j]’s value to zero if its value is 2.

Here is how the matrix will look after pre processing and after the completion of the algorithm.

## Source Code for Matrix Transformation to make rows and columns zero

I will provide the source code for the second method only, you can always code it for the first method as it is much more simpler than the second one.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
private void rowsAndColumnsToZero(int[][] A) { for (int i = 0; i < A.length; i++) { for (int j = 0; j < A[i].length; j++) { if (A[i][j] == 0) { markRow(A, i, 2); markColumn(A, j, 2); } } } for (int i = 0; i < A.length; i++) { for (int j = 0; j < A[i].length; j++) { if (A[i][j] == 2) { A[i][j] = 0; } } } } private void markRow(int[][] A, int i, int val) { for (int k = 0; k < A[i].length; k++) if (A[i][k] != 0) A[i][k] = val; } private void markColumn(int[][] A, int i, int val) { for (int k = 0; k < A.length; k++) if (A[k][i] != 0) A[k][i] = val; } |

Please download the complete source from github

## Analysis

##### First Approach

**Runtime Complexity :** We iterate through the matrix one time just to pre process, which means it is O(M*N) also, we traverse the matrix one more time to mark all the qualifying cells as zeroes. So the time complexity is of order O(M*N)

**Space Complexity :** The space needed is M + N, so we can say that the space complexity is O(M+N).

##### Second Approach

**Runtime Complexity :** We iterate through the matrix one time just to pre process, in which we also mark each of the cell and column with a value 2 if conditions are satisfied. Hence the runtime is O(M*N*M) considering M > N. Or we can say O(M^{2}N).

**Space Complexity :** The space needed not more than some counters so it is constant. O(1).

Don’t forget to **subscribe to TechieMe** to get updates on latest posts.