A Boolean Matrix Question

Given an matrix of zero's and ones if 1 is present at a[i][j] then make all elements in ith row and jth column to 1's.

Input:
1 0
0 0

Output:
1 1
1 0

Solution 1 (Using two temporary arrays): T: O(m*n) S:O(m+n)

   If we find  element 1  in the matrix then its row and column elements  will be 1. We will have two auxiliary arrays row[m] and column[j]. We will iterate through all the elements, if we find 1 in a[i][j] then we will set row[i] = 1 and column[j]=1.
  Then we will iterate through elements and if the row or column value is set to one then that element's value is set to 1.

Code:

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        int[][] a = {{1,0},{0,0},{0,0}};
        int m = a.length;
        int n = a[0].length;
        int[] row = new int[m];
        int[] col = new int[n];
     
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(a[i][j] == 1){
                    row[i] = 1;
                    col[j] = 1;
                }
            }
        }
     
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(row[i]==1 || col[j]==1){
                    a[i][j] = 1;
                }
            }
        }
     
       for(int i=0; i<m; i++){
           for(int j=0; j<n; j++){
               System.out.print(a[i][j]+" ");
           }
           System.out.println();
       }
     
     
}
}


Solution 2: (Without using temporary arrays) T:O(m*n) S: O(1)

   Here we are using first row and first column like temporary arrays above. In the first phase if ,
a[i][j] = 1, then we will set a[0][j] = 1 and a[i][0]=1. If the element a[i][j] is 1 then it will effect in first row, first column in addition to other indices. Hence in first iteration we will update only the first row and first column. In the consequent phase we will update other rows and columns referring first row and first column.
   Initially if 1 is present in either first row or first column it will have effect on the entire first row or first column. In the first phase itself we set values firstrow1 and firstcolumn1.
  Then after updating other rows we will finally update firstrow and firstcolumn with respect to the the set boolean values.

Code:

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        int[][] a = {{1, 0, 0, 1},
                {0, 0, 1, 0},
                {0, 0, 0, 0}};;
        int m = a.length;
        int n = a[0].length;
        boolean firstrow1  =false;
        boolean firstcolumn1 = false;
       
        System.out.println("input: ");
        for(int i=0; i<m; i++){
           for(int j=0; j<n; j++){
               System.out.print(a[i][j]+" ");
           }
           System.out.println();
       }
       
       
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 && a[i][j]==1){
                    firstrow1 = true;
                }
                if(j==0 && a[i][j]==1){
                    firstcolumn1 = true;
                }
               
                if(a[i][j] == 1){
                    a[i][0] = 1;
                    a[0][j] = 1;
                }
            }
        }
       
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(a[i][0]==1 || a[0][j]==1){
                    a[i][j] =1;
                }
            }
        }
       
        if(firstrow1){
            for(int i=0; i<n; i++){
              a[0][i] = 1;
            }
        }
       
        if(firstcolumn1){
            for(int i=0; i<m; i++){
                a[i][0] = 1;
            }
        }
       
        System.out.println("Output: ");
       for(int i=0; i<m; i++){
           for(int j=0; j<n; j++){
               System.out.print(a[i][j]+" ");
           }
           System.out.println();
       }
     
       
}
}

Output:

input: 
1 0 0 1 
0 0 1 0 
0 0 0 0 
Output: 
1 1 1 1 
1 1 1 1 
1 0 1 1