Arrays-String interview question 8

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 8

Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to O.
Solution: You can find the solution for this problem here.
Solution 1 using java.
In this problem we are setting the elements in the particular column and row to zero if any element in that particular row or column is already zero initially. Here first we have to check which of the elements are initially zero in the matrix and save their row and column number in an array then we write a function to make all the elements of the particular row to zero and another function to make all the elements of the particular column to zero.

• So we have to write 3 functions
• To find the elements that are zero and and note their row and column in which they occur.
• next we have to write the function that make all the element of a particular row zero.
• and last function that make all the elements in the particular column to zero.
• This problem is very unique and easy as well just need a focus mind and little practice to solve this problem.

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int matrix[][]={{1,2,3},{4,5,6},{7,8,0}};
array(matrix);
for(int i=0;i<matrix.length;i++)
  {
   for(int j=0;j<matrix[0].length;j++)
   {
    System.out.print(matrix[i][j]);
   }
   System.out.println("");
  }
 }
 public static void array(int a[][])
 {
  int[] row = new int[a.length];
  int[] col = new int[a[0].length];
  int i=0,j=0;
  for(i=0;i<a.length;i++)
  {
   for(j=0;j<a[0].length;j++)
   {
    if(a[i][j]==0)
    {
     row[i]=1;
     col[j]=1;
    }
   }
  }
  //row nullfy
  for(i=0;i<row.length;i++)
  {
   if(row[i]==1)
   {
    for(j=0;j<a[i].length;j++)
    {
     a[i][j]=0;
    } 
   }
  }
  //column nullfy
  for(i=0;i<col.length;i++)
  {
   if(col[i]==1)
   {
    for(j=0;j<a.length;j++)
    {
     a[j][i]=0;
    } 
   } 
  }
 }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.
Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.