DP #41. Matrix subsquare with all surrounding X - mbhushan/dynpro GitHub Wiki

(41). Maximum Subsquare With Sides as X in a matrix.

Find maximum subsquare in a matrix made up of Xs and Os such that 
all four sides of subsquare are Xs. It does not matter what is inside 
the subsquare. All 4 sides should be made up entirely of Xs.

Approach:

a. keep another bookkeeping matrix with each cell defined 
as Node(horizontal, vertical)
b. horizontal is number of "X" seen so far horizontally and 
vertical is number of "X" seen so far vertically.
c. once the book keeping matrix is complete, we check each Node and 
keep a running max subsquare matrix seen so far.
d. We get subsquare by getting min of (horizontal, vertial) at each node
 and checking if subsquare can be formed from value min to 1.

Formula:

//populate book keeping matrix.
for (int i=1; i<row; i++) {
			for (int j=1 ; j<col; j++) {
				Node node = new Node(0, 0);
				if (M[i][j] == 'X') {
					node.horizontal = T[i][j-1].horizontal + 1;
					node.vertical = T[i-1][j].vertical + 1;
				}
				T[i][j] = node;
			}
		}
===================================================
//Finding max subsquare matrix
for (int i=row-1; i>0; i--) {
			for (int j=col-1; j>0; j--) {
				Node node = T[i][j];
				int range = Math.min(node.horizontal, node.vertical);
				for (int k=range; k>1; k--) {
					if (T[i][j-k+1].vertical >= k && T[i-k+1][j].horizontal >= k) {
						maxSquare = Math.max(maxSquare, k);
						break;
					}
				}
			}
		}
============================
class Node {
	int horizontal;
	int vertical;
	
	public Node (int h, int v) {
		this.horizontal = h;
		this.vertical = v;
	}
}

input
	0	0	0	0	0	X
	0	X	0	X	X	X
	0	X	0	X	0	X
	0	X	X	X	X	X
	0	X	X	0	0	0
(hor,ver)
	(0,0)	(0,0)	(0,0)	(0,0)	(0,0)	(1,1)
	(0,0)	(1,1)	(0,0)	(1,1)	(2,1)	(3,2)
	(0,0)	(1,2)	(0,0)	(1,2)	(0,0)	(1,3)
	(0,0)	(1,3)	(2,1)	(3,3)	(4,1)	(5,4)
	(0,0)	(1,4)	(2,2)	(0,0)	(0,0)	(0,0)

Max subsquare with X border

• Time Complexity: O(n*m)
• Space Complexity: O(n*m)