Categories

# Find the maximum size of square of side ‘X’ in a matrix

We use dynamic programming to solve this.
Space complexity = O(2*n)
Time complexity = O(n^3).

```public class maxSquareX {
public static void main(String[] args) {

char[][] input = {
{ 'X', '0', 'X', 'X', 'X' },
{ 'X', 'X', 'X', 'X', 'X' },
{ 'X', 'X', '0', 'X', '0' },
{ 'X', 'X', 'X', 'X', 'X' },
{ 'X', 'X', 'X', '0', '0' },
};

int[][] rows = new int[input.length][input[0].length];
int[][] cols = new int[input.length][input[0].length];

for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input[0].length; j++) {
if (input[i][j] == '0') {
rows[i][j] = cols[i][j] = 0;
} else {
rows[i][j] = (i == 0) ? 1 : rows[i - 1][j] + 1;
cols[i][j] = (j == 0) ? 1 : cols[i][j - 1] + 1;
}
}
}
int max = 1; // since this is the minimum answer we can get int small;
// Start from bottom right
for (int i = input.length - 1; i >= 0; i--) {
for (int j = input[0].length - 1; j >= 0; j--) {
small = Math.min(rows[i][j], cols[i][j]);
while (small > max) {
// we use index [j - small + 1] because small might be
// input.length + 1 and when that is subtracted from 'j' we
// might get an 'ArrayIndexOutOfBoundsException'.
if (small <= rows[i][j - small + 1] && small <= cols[i - small + 1][j]) {
max = small;
} else
small--;
}
}
}
}
}```

Output

```3
```