Microsoft Interview Question
Software EngineersCountry: United States
If we have O(1) space, I only came up with the solution using 2 passes (can it be improved ?)
the basic idea is: we need to choose some "junk" row and column to save the locations
of 0s in them. These junk row/col can be any that will be zeroed out anyway. Then in the 2nd pass, we just go over the whole matrix once again and zero out elements based on 0 pattern in our "junk" row/col:
#define NROWS 5
#define NCOLS 5
int A[NROWS][NCOLS] = {
{1,1,1,0,1},
{1,1,0,1,1},
{1,1,1,1,1},
{1,0,1,0,1},
{1,1,1,1,1}};
void print_matrix() {
printf("A = \n");
for(int i = 0; i < NROWS; i++) {
for(int j = 0; j < NCOLS; j++){
printf("%d ", A[i][j]);
}
printf("\n");
}
printf("\n\n");
}
void compute() {
// these row/col will be used to keep track of zeros in the matrix
int junk_row = -1,
junk_col = -1;
for(int i = 0; i < NROWS; i++) {
for(int j = 0; j < NCOLS; j++) {
if(A[i][j] == 0) {
// choose our junk row/col if they are not set yet
if(junk_row == -1) {
junk_row = i;
junk_col = j;
}
// set markers where we need to zero out
A[junk_row][j] = 0;
A[i][junk_col] = 0;
}
}
}
if(junk_row != -1) {
for(int i = 0; i < NROWS; i++) {
for(int j = 0; j < NCOLS; j++) {
// do not zero-out junk column/row !!
if(j == junk_col || i == junk_row)
continue;
A[i][j] &= (A[junk_row][j] & A[i][junk_col]);
}
}
// zero-out junk column/row
for(int i = 0; i < NROWS; i++)
A[i][junk_col] = 0;
for(int j = 0; j < NCOLS; j++)
A[junk_row][j] = 0;
}
}
int main() {
print_matrix();
compute();
print_matrix();
return 1;
}
can you give some more information on your approach?
are you suggesting to use disjoint set...will it not be O(n) space?
The trick here is how to remember which cells had zeros in the original matrix vs which cells were set by the function/method as
we traverse along the metrix row by row.
We would violate the space O(1) constraint if we use a new data structure for this purpose.
So solution for this is a combination of the following actions
1. Replace zeros in cells not traversed yet with -1 when we set row or column to zero.
2. When we encounter a -1 later as we traverse, we will check whether the row or column was set to zero previously to confirm whether the -1 was a zero we memorized or whether it is a -1 in the originzl matrix.
3. Use the first row to keep track whether a column was set to zero or not.
4. Since we use the first row to keep track zero columns, we first check whether the first row has any zeros to begin with
5. after processing and setting all rows, set the first row to zero if there were any zeros at the begining
pseudocode
1. traverse first row
2. if there is a zero in a column
3. set firstRowHasZero = true
4. set non zero values in column to zero and zero values to -1
5. traverse each remaining row
6. set rowAlreadyReset = false
7. if a zero is in a column
8 or if (-1 is in a column and firstrow[column] has zero) //the column was set to zero and the current cell has a original zero
9 or if (-1 is in a column and rowAlreadyReset) //the row was set to zero and the current cell has a original zero
10. set rowAlreadyReset = true
11. set non zero values in column to zero and non visited zero values to -1
12. set non zero values in row to zero and non visited zero values to -1
13. if firstRowHasZero
14. set first row to zero
C# implementation
public int[,] ProcessMatrix(int[,] matrix)
{
const int firstRow = 0; //used for code readability
const int firstColumn = 0; //used for code readability
int lookupValue = 0; //Value to find
int altLookupValue = -1; //Value used to memorize original zeros not parsed yet
int row = firstRow;
int column;
int rowCount = matrix.GetLength(0);
int columnCount = matrix.GetLength(1);
bool rowAlreadyReset = false; //used to avoid repeated rewrite of zero
bool firstRowHasZero = false;
if (rowCount > 0)
{
//Check whether first row has zero and also set columns to zero if zero encountered
for (column = firstColumn; column < columnCount; column++)
{
if (matrix[row, column] == lookupValue) //original zero encountered
{
firstRowHasZero = true;
//Set down cells to 0 if non zero and -1 if zero
AltResetCellsInColumn(matrix, column, row + 1, rowCount, altLookupValue);
}
}
//Process second row onwards
for (row++; row < rowCount; row++)
{
rowAlreadyReset = false;
for (column = firstColumn; column < columnCount; column++)
{
//check whether the column was previously identified to have zero
bool columnAlreadyReset = (matrix[firstRow, column] == lookupValue);
//Is the cell an Original Zero
if (((matrix[row, column] == lookupValue) //found a 0
&& (!(rowAlreadyReset //this zero is not due to a row reset
|| columnAlreadyReset) //or column reset
)
)
|| ((matrix[row, column] == altLookupValue) //found a -1
&& (columnAlreadyReset //is this -1 due to a column reset
||(rowAlreadyReset)) //or a row reset
))
{//found a original 0
if (!rowAlreadyReset)
{
//set all left cells to zero
ResetCellsInRow(matrix, row, firstColumn, column);
//Set right cells to 0 if non zero and -1 if zero
AltResetCellsInRow(matrix, row, column + 1, columnCount, altLookupValue);
rowAlreadyReset = true;
}
else if (!columnAlreadyReset)
{
//Set all cells above to zero, this will flag column reset because it update row 1
ResetCellsInColumn(matrix, column, firstRow, row);
//Set down cells to 0 if non zero and -1 if zero
AltResetCellsInColumn(matrix, column, row + 1, rowCount, altLookupValue);
}
//make sure we overwrite temporary -1 values
matrix[row, column] = 0;
}
}
}
if (firstRowHasZero)
{
//set all records in the first row to zero if first row had zeros orignially
for (column = firstColumn; column < columnCount; column++)
{
matrix[firstRow, column] = lookupValue;
}
}
}
return matrix;
}
//Set the value of all cells between start index and end index in the row to zero
private void ResetCellsInRow(int[,] matrix, int row, int start, int end)
{
for (; start < end; start++)
{
matrix[row, start] = 0;
}
}
//Set the non zero value of all cells between start index and end index in the row
//to zero. Set zero values to -1 to memorize it for latter processing
private void AltResetCellsInRow(int[,] matrix, int row, int start, int end, int altValue)
{
for (; start < end; start++)
{
//If the cell is zero then set it to -1 to memorize it for latter processing
if (matrix[row,start] == 0)
{
matrix[row, start] = altValue;
}
else
{
matrix[row, start] = 0;
}
}
}
//Set the value of all cells between start index and end index in the column to zero
private void ResetCellsInColumn(int[,] matrix, int column, int start, int end)
{
for (; start < end; start++)
{
matrix[start, column] = 0;
}
}
//Set the non zero value of all cells between start index and end index in the column
//to zero. Set zero values to -1 to memorize it for latter processing
private void AltResetCellsInColumn(int[,] matrix, int column, int start, int end, int altValue)
{
for (; start < end; start++)
{
//If the cell is zero then set it to -1 to memorize it for latter processing
if (matrix[start, column] == 0)
{
matrix[start, column] = altValue;
}
else
{
matrix[start, column] = 0;
}
}
}
Here is a rather straightforward java solution which avoids recursion and runs in optimal time proportional to the size of the matrix(the number of elements).
public static void processMatrix(int[][] matrix) {
Set<Integer> visitedCol = new HashSet<>();
Set<Integer> visitedRow = new HashSet<>();
for (int row = 0; row < matrix.length; row++) {
if (visitedRow.contains(row)) continue;
for (int col = 0; col < matrix[row].length; col++) {
if (visitedCol.contains(col)) continue;
if (matrix[row][col] == 0) {
setEachRowEntryToZero(row, matrix);
setEachColEntryToZero(col, matrix);
visitedRow.add(row);
visitedCol.add(col);
break;
}
}
}
}
private static void setEachRowEntryToZero(int row, int[][] matrix) {
for (int i = 0; i < matrix[row].length; i++) {
matrix[row][i] = 0;
}
}
private static void setEachColEntryToZero(int col, int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
Here is a rather straightforward java solution which runs in time proportional to the number of entries in the matrix.
public static void processMatrix(int[][] matrix) {
Set<Integer> visitedCol = new HashSet<>();
Set<Integer> visitedRow = new HashSet<>();
for (int row = 0; row < matrix.length; row++) {
if (visitedRow.contains(row)) continue;
for (int col = 0; col < matrix[row].length; col++) {
if (visitedCol.contains(col)) continue;
if (matrix[row][col] == 0) {
setEachRowEntryToZero(row, matrix);
setEachColEntryToZero(col, matrix);
visitedRow.add(row);
visitedCol.add(col);
break;
}
}
}
}
private static void setEachRowEntryToZero(int row, int[][] matrix) {
for (int i = 0; i < matrix[row].length; i++) {
matrix[row][i] = 0;
}
}
private static void setEachColEntryToZero(int col, int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
#include <iostream>
#include <vector>
typedef std::vector<int> ROW_TYPE;
typedef std::vector<ROW_TYPE> MATRIX_TYPE;
void MakeMatrixColoumnValuesZero(MATRIX_TYPE& matrix, int i, int j)
{
for (int k = i - 1; k >= 0; --k)
{
matrix[k][j] = 0;
}
}
void MakeMatrixRow0(MATRIX_TYPE& matrix, int i)
{
int coloumnCount = matrix[0].size();
for (int j = 0; j < coloumnCount; ++j)
{
matrix[i][j] = 0;
}
}
int FindLastIndexInMatrixColoumnThatIsZero(const MATRIX_TYPE& matrix, int j)
{
int rowCount = matrix.size();
for (int i = 0; i < rowCount; ++i)
{
if (matrix[i][j] != 0)
{
return i - 1;
}
}
}
void ProcessMatrix(MATRIX_TYPE& matrix)
{
int rowCount = matrix.size();
int coloumnCount = matrix[0].size();
for (int i = 0; i < rowCount; ++i)
{
for (int j = 0; j < coloumnCount; ++j)
{
if (matrix[i][j] == 0)
{
MakeMatrixColoumnValuesZero(matrix, i, j);
}
}
}
for (int i = 0; i < rowCount; ++i)
{
for (int j = 0; j < coloumnCount; ++j)
{
if (matrix[i][j] == 0 && i == FindLastIndexInMatrixColoumnThatIsZero(matrix, j))
{
MakeMatrixRow0(matrix, i);
MakeMatrixColoumnValuesZero(matrix, rowCount, j);
}
}
}
}
int main()
{
MATRIX_TYPE matrix;
ROW_TYPE row = { 1, 2, 3, 4, 5 };
matrix.push_back(row);
row = { 2, 0, 4, 6, 6 };
matrix.push_back(row);
row = { 2, 3, 4, 0, 6 };
matrix.push_back(row);
row = { 2, 7, 4, 6, 6 };
matrix.push_back(row);
row = { 2, 7, 4, 6, 6 };
matrix.push_back(row);
int rowCount = matrix.size();
int coloumnCount = matrix[0].size();
for (int i = 0; i < rowCount; ++i)
{
for (int j = 0; j < coloumnCount; ++j)
{
std::cout << matrix[i][j] << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
ProcessMatrix(matrix);
for (int i = 0; i < rowCount; ++i)
{
for (int j = 0; j < coloumnCount; ++j)
{
std::cout << matrix[i][j] << " ";
}
std::cout << std::endl;
}
}
We can use one integer O(n) in binary format (e.g.: 0b01101) to save which row or columns need to be set to zero during first full scan. Position 0->N used for columns, and N+1->M for rows, and 1 means to set to zero. And with the integer we can set the rows/columns to zero directly. The sample code is below:
int pos = 0; // Low bits for columns
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
if (matrix[r][c] == 0)
{
// Save bits
pos |= (1 << c);
pos |= (1 << (r + cols));
}
}
}
for (int c = 0; c < cols && pos > 0; c++)
{
if (0 < (pos & (1 << c)))
{
for (int r = 0; r < rows; r++)
{
matrix[r][c] = 0;
}
}
}
for (int r = 0; r < rows && pos > 0; r++)
{
if (0 < (pos & (1 << (cols + r))))
{
for (int c = 0; c < cols; c++)
{
matrix[r][c] = 0;
}
}
}
package com.shortestPath;
public class CodeMatrix {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int m[][]={{1, 2 , 3,1},{5 , 6, 0,1 },{9, 10, 1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;
int f[][]=m;
int n=r-1;
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.println("==="+i+":::::"+j);
if(m[i][j]==0)
{
while(flag)
{
//System.out.println(col+"::"+n+":::::"+j);
try{
f[i][col]=0;
}
catch(Exception e){
}
try{
f[n][j]=0 ;
}
catch(Exception e){
}
col--;
n--;
max--;
if(max<0)flag=false;
}
}
}
}
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.print(" "+f[i][j]);
}
System.out.println(" ");
}
}
}
package com.shortestPath;
public class CodeMatrix {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int m[][]={{1, 2 , 3,1},{5 , 6, 0,1 },{9, 10, 1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;
int f[][]=m;
int n=r-1;
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.println("==="+i+":::::"+j);
if(m[i][j]==0)
{
while(flag)
{
//System.out.println(col+"::"+n+":::::"+j);
try{
f[i][col]=0;
}
catch(Exception e){
}
try{
f[n][j]=0 ;
}
catch(Exception e){
}
col--;
n--;
max--;
if(max<0)flag=false;
}
}
}
}
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.print(" "+f[i][j]);
}
System.out.println(" ");
}
}
}
public class CodeMatrix {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int m[][]={{1, 2 , 3,1},{5 , 6, 0,1 },{9, 10, 1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;
int f[][]=m;
int n=r-1;
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.println("==="+i+":::::"+j);
if(m[i][j]==0)
{
while(flag)
{
//System.out.println(col+"::"+n+":::::"+j);
try{
f[i][col]=0;
}
catch(Exception e){
}
try{
f[n][j]=0 ;
}
catch(Exception e){
}
col--;
n--;
max--;
if(max<0)flag=false;
}
}
}
}
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.print(" "+f[i][j]);
}
System.out.println(" ");
}
}
}
int m[][]={{1, 2 , 3,1},{5 , 6, 0,1 },{9, 10, 1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;
int f[][]=m;
int n=r-1;
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.println("==="+i+":::::"+j);
if(m[i][j]==0)
{
while(flag)
{
//System.out.println(col+"::"+n+":::::"+j);
try{
f[i][col]=0;
}
catch(Exception e){
}
try{
f[n][j]=0 ;
}
catch(Exception e){
}
col--;
n--;
max--;
if(max<0)flag=false;
}
}
}
}
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.print(" "+f[i][j]);
}
System.out.println(" ");
}
}
int m[][]={{1, 2 , 3,1},{5 , 6, 0,1 },{9, 10, 1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;
int f[][]=m;
int n=r-1;
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.println("==="+i+":::::"+j);
if(m[i][j]==0)
{
while(flag)
{
//System.out.println(col+"::"+n+":::::"+j);
try{
f[i][col]=0;
}
catch(Exception e){
}
try{
f[n][j]=0 ;
}
catch(Exception e){
}
col--;
n--;
max--;
if(max<0)flag=false;
}
}
}
}
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.print(" "+f[i][j]);
}
System.out.println(" ");
}
}
int m[][]={{1, 2 , 3,1},{5 , 6, 0,1 },{9, 10, 1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;
int f[][]=m;
int n=r-1;
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.println("==="+i+":::::"+j);
if(m[i][j]==0)
{
while(flag)
{
//System.out.println(col+"::"+n+":::::"+j);
try{
f[i][col]=0;
}
catch(Exception e){
}
try{
f[n][j]=0 ;
}
catch(Exception e){
}
col--;
n--;
max--;
if(max<0)flag=false;
}
}
}
}
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.print(" "+f[i][j]);
}
System.out.println(" ");
}
}
Are you sure this is possible? I don't think you can do it in just one pass. You can't set the elements in a row and column to zero as you go. If you do, you'll just end up setting the entire matrix to 0
You are right, I don't see how we can solve this in a single pass. I think the solution I suggested does it in 2 passes. There's an O(n^2) solution as well but that too doesn't solve it in a single pass.
with the help of recursion i can read once each array and put it in stack and once i find a zero i will go on writing till the length of i and j and agin from the position i found the zero till the recursion stack is empty
I think this is a trick. If one element in the matrix is 0, then the entire matrix will have only zeros. So just search for a zero and return a matrix with zeros.
ArrayList colArr = new ArrayList();
for(int row = 0; row< totalRows; row++)
{
for(int col= 0; col< totalCols; col++)
{
if ( matrix[i][j] == 0)
{
makeRowZero(row);
colArr.add(col);
break;
}
}
}
makeColZero(colArr );
If it is o(n) memory, then lets do this:
1. Create an array of same size, say n * n, with all elements set to logic 1. Let's call it array B.
2. Iterate through every element in the initial matrix, lets call it array A. When see a zero, set the corresponding entry in B matrix to zero, and also every element in the same row and column in B.
3. And matrix A and B. This should set all the right entries in A to zero.
It is doing more than one pass on B for sure, but only one pass on A. Hahaha
With space complexity of O(1), it got a little trickier.
- justaguy September 17, 2015I can think of 2 approaches:
1. Use a Point Class for matrix, with int oldvalue and int newvalue as variables. Initially both values will be the same. We only retrieve and set newvalue, that way we can check for zero in the oldvalue.
2. If we are not allowed to have point class then we would have to set zeros as we go along.
While we are traversing the matrix, for each point first CheckIfPrevRowsAreZero()
i.e check if a[0][j]..a[i-1][j] are zeros, if they are then set a[i][j] to zero. Once we are done with that check and if prev. rows are not zero then check if value of a[i][j] is zero, if it is set all the values in that row to zero and skip the row and go to the next one right away then repeat.
Running time is not that great. Its O(n^3)