Maximum submatrix

a) There is a square of nxn size which is comprised of n-square 1x1 squares. Some of these 1x1 squares are colored. Find the biggest subsquare which is not colored.

b) Also asked to extend it to find the biggest area rectangle.

OR

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  1  1  1
   1  1  1  1  1
   0  0  0  0  0
The maximum square sub-matrix with all set bits is

    1  1  1
    1  1  1
    1  1  1

Approach:
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[][]
For the given M[R][C] in above example, constructed S[R][C] would be:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  1
   1  2  2  3  2
   0  0  0  0  0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.

To find the biggest rectangle:
R0   0  1  1  0  1
R1   1  1  0  1  0
R2   0  1  1  1  1
R3   1  1  1  1  1
R4   1  1  1  1  1
R5   0  0  0  0  0

Rij denote Ri & Rj
R01 = 0 1 0 0 0 (max area of rect so far: 1*2 = 2)
R12 = 0 1 0 1 0 (max area of rect so far: 1*2 = 2)
R23 = 0 1 1 1 1 (max area of rect so far: 4*2 = 8)
R34 = 1 1 1 1 1 (max area of rect so far: 5*2 = 10)
R45 = 0 0 0 0 0  (max area of rect so far: 10)

Again lets do the same & operation between consecutive rows above.

R02 = 0 1 0 0 0 (local area: 1*3=3, max so far: 10)
R13 = 0 1 0 1 0 (local area: 1*3=3, max so far: 10)
R24 = 0 1 1 1 1 (local area: 4*3=12, new max so far: 12)
R35 = 0 0 0 0 0 (local area: 0*0=0, new max so far: 12)

R03 = 0 1 0 0 0 (max so far: 12)
R14 = 0 1 0 1 0 (max so far: 12)
R25 = 0 0 0 0 0 (max so far: 12)

again repeat
R04 = 0 1 0 0 0 (max so far: 12)
R15 = 0 0 0 0 0 (max so far: 12)

finally,
R05 = 0 0 0 0 0

And max area of rectangle so far = 12.

Unique Rows in a Matrix.

Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays
eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0


Approach:
1. Build a String from each row of the matrix, where each element is separated from another by a space.
2. store the string in a hashset.
3. in the end read the hashset and construct the matrix, the rows would be the unique ones.


Code input/output:
Input matrix is: 
0 1 0 0 1 
1 0 1 1 0 
0 1 0 0 1 
1 1 1 0 0 
Unique Rows are: 
0 1 0 0 1 
1 1 1 0 0 
1 0 1 1 0 

Rotate a square matrix counter clockwise by 90 degrees.

Given a KxK array, rotate the array 90 degrees counter-clockwise in place.


Code output:



Original Square Matrix: 
1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 


Transpose of the square matrix: 
1 5 9 13 
2 6 10 14 
3 7 11 15 
4 8 12 16 


Matrix Rotated by 90 degrees counter clockwise:
4 8 12 16 
3 7 11 15 
2 6 10 14 
1 5 9 13 

Maximum sum submatrix of a given Matrix.

Approach:

Find an element in a matrix, whose rows are sorted left to right and cols are sorted top to bottom

Input:
3
3
1 2 3
4 5 6
7 8 9
7
Output:
1 2 3
4 5 6
7 8 9
KEY:7
Key Search? true


Code: