# Matrix Transformation to make rows and columns zero

## 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 ATransform 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 XM and YN. Then we traverse through the matrix and for each cell A[i][j] if it is zero them we store 1 at the ith index of XM and to the jth index of YN. Once we are done with this pre processing, we just need to traverse through XM and YN 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.
```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;
}
```