CareerCup

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).

public static void nullify(int[][] arr){
		if (arr==null){return;}
		
		boolean nullifyFirstRow = false;
		boolean nullifyFirstColumn = false;
		
		for (int i=0;i<arr.length;i++){
			if (arr[i]==null){return;}
			for (int j=0;j<arr[i].length;j++){
				if (arr[i][j]==0){
					arr[i][0]=0;arr[0][j]=0;
					if (i==0){nullifyFirstRow=true;}
					if (j==0){nullifyFirstColumn=true;}
				}
			}
		}
		
		for (int i=1;i<arr.length;i++){
			for (int j=1;j<arr[i].length;j++){
				arr[i][j] = ((arr[i][0]==0) || (arr[0][j]==0)) ? 0 : arr[i][j];
			}
		}
		
		for (int i=0;i<arr.length;i++){arr[i][0] = (nullifyFirstColumn) ? 0 : arr[i][0];}
		for (int j=0;j<arr[0].length;j++){arr[0][j] = (nullifyFirstRow) ? 0 : arr[0][j];}
	}

Complexity: O(mn) run-time complexity and O(1) space complexity.

// 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;
				}
			}
		}
	}

Approach:

-First find out all the row and column which has at-least one occurrence of '0'
--We can search row by row and save row and column value in two separate arrays
-Than make all rows and columns '0' as per above step result

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

for(int i=0;i<arr.length;)
{if(true)
{
for(int j=0;j<arr.length;j++)
{
if(arr[i][j]==0)
{
for(int k=0;k<arr.length;k++)
{
arr[i][k]=0;
}
for(int k=0;k<arr.length;k++)
{
arr[k][j]=0;
}

}i++;

}
}
continue;
}

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;
}
}

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();
}}