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.
Matrix Transformation to make rows and columns zero
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.
Matrix Transformation to make rows and columns zero

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.

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(M2N).
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.

  • Saurabh Vats

    It's possible in time O(M*N) and space O(1). You need to use any 1 row+col combo as virtual auxiliary space, preferably the last or first. Nice visuals πŸ™‚

    • Thank you for the suggestion… I would request you to please add a code for other users πŸ™‚

      • Saurabh Vats

        The method goes very similar to the one with extra space(Approach 1). I would rather try to explain in steps:
        1) Lets for simplicity, we choose to select 1st RC combo as auxiliary space. i.e row=1, column=1.
        2) Now we pre-process for just first row and first column and store the result in some variable r1, c1.
        3) Now we use the row 1 and column 1 as auxiliary space for processing next {M-1,N-1} matrix left.
        4) Now we fill back values for row 1 and column 1 depending upon values of r1 and c1.

        Note: It's basically the same stuff we use to save space in the dynamic programming problems where the dependency met is just for constant previous memoized indices.

        Let me know in case it's not clear enough πŸ™‚

        • Its perfectly clear… I was trying not to take the pain of writing the new code suggested by you. Hope people understand this comment. If not I will edit this article once I have some time. πŸ™‚

          • Saurabh Vats

            ^Yes the approach looks similar to me. Compared to images you put on here, I figure out the pain of writing code to be much lesser. Good luck πŸ™‚