Coding Challenge Day-5: Problem 1: If an element in an MxN matrix is zero, it’s entire row and column are set to zero

Hello! So I’m doing a 30 day coding challenge where I solve a few questions every day and thought of posting them here on my blog so that you guys can join the challenge too!

Welcome to Coding challenge Day 5: Problem 1! Be sure to post your answers, queries etc in the comments!!

Problem: Write an Algorithm such that if an element in an MxN matrix is zero, it’s entire row and column are set to zero

Sample input: int [][] array= {{1,0,2,4}, {8,9,4,3}, {5,6,9,1}};
Output: 0 0 0 0
8 0 4 3
5 0 9 1

Solution:

  • so start by creating two boolean type arrays for marking which rows and columns have the number zero.
  • run a loop through entire matrix to find which rows and columns contain zero
  • run two loops which each send the zero-containing row and column numbers to function change_row_zero and change_column_zero respectively
package array;
// Write an algorithm such that if an element in an MxN matrix is 0, it's entire row and column are set to zero
public class Program004zero_replacement {
	
	public static void check_zero (int array[][], int M, int N){	
		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(array[i][j]==0){
				row[i]=true;
				column[j]= true;
			}
		}
	}
	  
	  for(int i=0; i<row.length; i++){
		  if(row[i])
			  change_row_zero(array, i, N);
	  }
	  
	  for(int i=0; i<column.length; i++){
		  if(column[i])
			  change_column_zero(array, i, M);
	  }
	}
	
	
	public static void change_row_zero (int [][]array, int row, int N){
		for(int i=0; i<N; i++){
			array[row][i]=0;
		}
		
	}
	
	public static void change_column_zero (int [][] array, int col, int M){
		for(int j=0; j<M; j++){
			array[j][col]=0;
		}
	}
	
	public static void display_matrix (int array[][], int M, int N){
		for (int i=0; i<M; i++){
			for (int j=0; j<N; j++){
				System.out.printf("%2d", array[i][j]);
			}
			System.out.println();
		}
	}
	
	public static void main ( String args[]){
		int [][] array= {{1,0,2,4}, {8,9,4,3}, {5,6,9,0}};
		int row= array.length;
		int column = array[0].length;
		check_zero(array, row, column);
		display_matrix(array, row,column);
		
	}

}

Download Code

Refernces:
1. Cracking the Coding Interview (by Gayle Laakmann McDowell)

Happy learning!!

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: