Oracle Interview Question
Software Engineer / Developers// Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
// COMPLEXCITY O (NM)
public static void setZero(int M[][]){
boolean rows [] = new boolean[M.length];
boolean columns[] = new boolean[M[0].length];
for(int i = 0; i < M.length; i++){
for(int j = 0; j < M[i].length; j++){
if(M[i][j] == 0 ){
rows[i] = true;
columns[j] = true;
}
}
}
for(int i = 0; i < M.length; i++){
for(int j = 0; j < M[i].length ; j++){
if(rows[i] || columns[j]){
M[i][j] = 0;
}
}
}
}
Method to set all elements below and to the right are set to -1
void minusone(int a[][N], int M, int x,int y)
{
for(int i = x; i< N; i++)
for(int j=y; j<M; j++)
a[i][j] = -1;
}
Now call this function for any element that you encounter zero
for(int i =0; i <M; i++)
for(int j = 0; j<N; j++)
if( a[i][j] == 0 )
minusone(a, M, i, j);
Now find all -1s in an array and replace all of them with 0
import java.util.Arrays;
public class MatrixCalculation {
public static void main(String[] args) {
int M[][] =new int [][]{
{0,1,1,0},
{1,1,1,0},
{1,1,1,1} ,
{1,1,1,1}};
setZero(M);
}
public static void setZero(int M[][]){
boolean rows [] = new boolean[M.length];
boolean columns[] = new boolean[M[0].length];
for(int i = 0; i < M.length; i++){
for(int j = 0; j < M[i].length; j++){
if(M[i][j] == 0 ){
rows[i] = true;
columns[j] = true;
}
}
}
for(int i = 0; i < M.length; i++){
for(int j = 0; j < M[i].length ; j++){
if(rows[i] || columns[j]){
M[i][j] = 0;
}
}
}
System.out.println(Arrays.deepToString(M));
}
}
import java.util.Arrays;
public class MatrixCalculation {Public static void main(String[] args) {
int M[][] =new int [][]{{0,1,1,0}, {1,1,1,0}, {1,1,1,1} , {1,1,1,1}};
setZero(M);
}
public static void setZero(int M[][]){
boolean rows [] = new boolean[M.length];
boolean columns[] = new boolean[M[0].length];
for(int i = 0; i < M.length; i++){
for(int j = 0; j < M[i].length; j++){
if(M[i][j] == 0 ){
rows[i] = true;
columns[j] = true;
}}}
for(int i = 0; i < M.length; i++){
for(int j = 0; j < M[i].length ; j++){
if(rows[i] || columns[j]){
M[i][j] = 0;
}}}
System.out.println(Arrays.deepToString(M));
}}
Here is my In place algorithm without using any extra variable:
for(int i =0;i<m;i++) {
for(int j=0;j<n;j++) {
if(a[i][j] == 0){
a[i][0] = 0;
a[0][j] = 0;
}
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(a[i][0] == 0 || a[0][j] == 0)
a[i][j] =0;
}}
for(int i =0;i<m;i++) {
for(int j=0;j<n;j++) {
System.out.print(a[i][j]);
}
System.out.println();
}}
It can be done with O(1) space complexity using the first row and column to mark whether an entire row/column should be nullified. We'll also keep two additional boolean values to determine whether the first row/column should be nullified as well (This is necessary because otherwise both of them will be nullified even if just one of them contains a 0).
Complexity: O(mn) run-time complexity and O(1) space complexity.
- IvgenyNovo January 26, 2014