CODEWITHSUNDEEP
javaalgorithmmatrix
salamanka44
salamanka44

Reputation: 944

Replace zero in a matrix in Java

I started to read the famous "cracking the Coding Interview" book and I want to do the following exercice.

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

Here is the author's solution :

public static void setZeros(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length;j++) {
        if (matrix[i][j] == 0) {
            row[i] = 1;
            column[j] = 1;
        }
    }
}

// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length; j++) {
        if ((row[i] == 1 || column[j] == 1)) {
             matrix[i][j] = 0;
        }
    }
 }
}

I agree with the author about the main idea. We don't have to store the position of '0' in the matrix but only the position of the rows and columns that are concernerd. But what I found a little "strange" in her solution is that at the end, she did a loop on all the cells of the matrix, which is not necessary in my opinion.

Here is my solution : 

static int[][] replaceMatrix(int[][] matrix){
  int M = matrix.length;
  int N = matrix[0].length;

  boolean[] row = new boolean[M] ;
  boolean[] column = new boolean[N];

  for (int i =0; i< M; i++) {
    for (int j = 0; j<N; j++ ){
         if (matrix[i][j] == 0) {
            row[i] = true;
            column[j] = true;
         }
    }
  }

  for (int i =0; i<M; i++){
    if (row[i]){
        for (int k =0; k<N; k++){
            matrix[i][k]=0;
        }
    }
  }

  for (int j =0; j<N; j++){
    if (column[j]){
        for (int k =0; k<M; k++){
            matrix[k][j]=0;
        }
    }
  }

I'am newbie in programmation so I'm not totaly sure about this. But in my solution, if we except the first step which is to store the 0 positions, my second part of my programme have a time complexity of O(M+N) while her solution has a complexity of O(M*N).

The problem is that the general complexity will be the same O(M*N + (M+N)) is the same that having the complexity O(2*M*N), no? (I'm not totally sure). For example, if it's a matrix with M=N, so the two complexity of the two programs will be O(M^2).

I really want to know if there is a difference or not about complexity in this case?

ps : I read that the space complexity can be improved with a bit vector. But I really didn't understand. Can you just give me a general idea about it (in Java)?

Upvotes: 3

Views: 2245

Answers (2)

Amit Dhar
Amit Dhar

Reputation: 31

Time complexity of your last two for loops is still O(M*N) as in worst case inner for loop will be running maximum value of k times.

Upvotes: 2

Sumeet
Sumeet

Reputation: 8292

There is technically no difference in your and the author's solution because both of you have traversed the entire matrix.So both codes are same ** if we have to consider big O notation**

In fact the author's code is a little bit( by little bit I do not mean a different time complexity) better. Here is the reason:

Suppose in your boolean array of rows, all rows are set true. Then in your case you will go through all rows and through each element of every row which is basically traversing the entire matrix.

Suppose in your boolean array of columns, all columns are set true. Then in your case you will go through all columns and through each element of every column which is basically traversing the entire matrix.

So you will in effect traverse the entire matrix twice. But the time complexity of the codes is the same because O(M*N) and O(2*M*N) is same.

You have already done saving space, since you used boolean data type.

Upvotes: 0

Related Questions