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

Turn an image by 90 degree

http://geeksforgeeks.org/?p=10402

Check code in this link : http://shashank7s.blogspot.com/2011/02/wap-for-square-matrix-rotation-by-90.html

Check transpose of a matrix

Maximum size square sub-matrix with all 1s

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
Algorithm:
Let the given binary matrix be M[R][C].
The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
     a) Copy first row and first columns as it is from M[][] to S[][]
     b) For other entries, use following expressions to construct S[][]
         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
   sub-matrix of M[][]
Java Code : 

public class MaxSubMatrix {
 public static void main(String[] args) {
  int[][] a = { 
                 { 0, 1, 1, 0, 1 }, 
                 { 1, 1, 0, 1, 0 }, 
                 { 0, 1, 1, 1, 0 },
                 { 1, 1, 1, 1, 0 }, 
                 { 1, 1, 1, 1, 1 }, 
                 { 0, 0, 0, 0, 0 } 
           };

  int rows = a.length;
  int columns = a[0].length;

  int[][] S = new int[rows][columns];

  // fill first row elements from a as it is
  for (int i = 0; i < columns; i++) {
   S[0][i] = a[0][i];
  }

  // similarly fill all elements in first column
  for (int i = 0; i < rows; i++) {
   S[i][0] = a[i][0];
  }

  // now calculate for other elements
  for (int i = 1; i < rows; i++) {
   for (int j = 1; j < columns; j++) {
    if (a[i][j] == 1)
     S[i][j] = getMinimum(S[i - 1][j], S[i][j - 1],
       S[i - 1][j - 1]) + 1;
   }
  }

  // Traverse the array and find the maximum value in array
  int maxSubMatrixSize = 0;
  int maxRowIndex = 0;
  int maxColumnIndex =0;
  for (int i = 0; i < rows; i++) {
   for (int j = 0; j < columns; j++) {
    if (S[i][j] > maxSubMatrixSize)
        maxSubMatrixSize = S[i][j];
        maxRowIndex= i;
        maxColumnIndex = j;
   }
  }
  System.out.println("Maximum size of submatrix with all ones : "
    + maxSubMatrixSize);
  System.out.println("Sub matrix starts from "+ (maxSubMatrixSize-1) + " positions above diagonally from position a["+maxRowIndex+"]["+maxColumnIndex+"]");   
 }

 private static int getMinimum(int a, int b, int c) {
  int min = a;
  if (a <= b && a <= c)
   min = a;
  else
   min = (b <= a && b <= c) ? b : c;
  return min;
 }

}

Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Auxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.

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