Matrices boolean set

A NxN binary matrix is given. If a row contains a 0 all element in the
row will be set to 0 and if a column contains a 0 all element of the
column will be set to 0. You have to do it in O(1) space.

example :

input array :

1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1

result array :

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0

Refer : http://www.geeksforgeeks.org/archives/14722

Approach I :

public class MatrixBitManipulation {
 public static void main(String[] args) {
  int[][] a = { { 0, 0, 0 }, { 0, 0, 1 }, { 0, 0, 0 } };
  printArray(a);
  modifyArray(a);
  System.out.println("after modifying the array : ");
  printArray(a);
 }

 public static void modifyArray(int[][] a) {
  if(a==null) return;
  int n = a.length;
  //boolean values used for identifying one is found in row or column
  boolean rowFound = false;
  boolean columnFound = false;
  // |(or) of all elements in first row and first column
  // a[0][0] = a[0][0 to n-1] | a[1 to n-1][0];
  if (a[0][0] == 1) {
   rowFound = true;
   columnFound = true;
  }
  for (int i = 1; i < n; i++) {
   if (a[0][i] == 1) {
    rowFound = true;
    break;
   }
  }

  for (int i = 1; i < n; i++) {
   if (a[i][0] == 1) {
    columnFound = true;
    break;
   }
  }

  for (int i = 1; i < n; i++) {
   for (int j = 1; j < n; j++) {
    a[0][i] |= a[j][i]; // a[0][i] contains | of all elements of ith
    // column
    a[i][0] |= a[i][j]; // a[i][0] contains | of all elements of ith
    // row
   }
  }

  for (int i = 1; i < n; i++) {
   for (int j = 1; j < n; j++) {
    a[i][j] = a[i][0] | a[0][j];
   }
  }

  if (rowFound) {
   // set all elements in the first row to 1
   for (int j = 0; j < n; j++) {
    a[0][j] = 1;
   }
  }

  if (columnFound) {
   // set all elements in the first column to 1
   for (int j = 0; j < n; j++) {
    a[j][0] = 1;
   }
  }
 }

 public static void printArray(int[][] a) {
  System.out.println();
  for (int i = 0; i < a.length; i++) {
   for (int j = 0; j < a.length; j++) {
    System.out.print("   " + a[i][j]);
   }
   System.out.println();
  }
 }
}

Approach II :

public abstract class MatrixManipulation {

 public static void main(String[] args) {
  int[][] a = { { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 } };
  printArray(a);
  modifyArray(a);
  System.out.println("after modifying the array : ");
  printArray(a);
 }

 public static void modifyArray(int[][] a) {
  if (a == null)
   return;
  int x=-1;
  int length = a.length;
  boolean row_1_found = false;
  for (int i = 0; i < length; i++) {
   for (int j = 0; j < length; j++) {
    if (a[i][j] == 1) {
     row_1_found = true;
     // process the column and set x if element is 0 else don't
     // process
     // if you find x, no need to process that column as it
     // already processed

     for (int k = 0; k < length; k++) {// a column is processed only once
      if (a[k][j] == 0) {
       a[k][j] = x;// assume x value is x(random number)
      } else if (a[k][j] == x) {
       break;// no need to process because this column is
       // already processed
      }
     }
    }
   }

   if (row_1_found) {// we found 1 in this row
    row_1_found = false;
    for (int j = 0; j < length; j++) {
     a[i][j] = 1;
    }
   }
  }

  for (int i = 0; i < length; i++) {
   for (int j = 0; j < length; j++) {
    if (a[i][j] == x) {
     a[i][j] = 1;
    }
   }
  }
 }

 public static void printArray(int[][] a) {
  System.out.println();
  for (int i = 0; i < a.length; i++) {
   for (int j = 0; j < a.length; j++) {
    System.out.print("   " + a[i][j]);
   }
   System.out.println();
  }
 }
}

http://www.mail-archive.com/algogeeks@googlegroups.com/msg14652.html