Maximum Size Square Sub Matrix with All 1's

$\mathtt{REFERENCE :}$HERE.

Problem Definition

Given a 2D $m \times n$ binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example

  Input 

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

  Output
  16

Solution 1: Naive Solution

The naive solution will be to find maximum size square from each of the cell considering them as the TOP-LEFT corner of the square and finally return the maximum size.

• Iterate through each of the cell in the given matrix
  • Consider each cell as the TOP-LEFT corner of a square. Then we go on to explore the maximum size square that it can form. The question is how do we explore?
    • If the current cell has value 0, then we don't need to explore at all. Size of square it can form is 0.
    • Else if the value is 1, then we go to the diagonally LEFT-DOWN cell. If this cell has value 1, then we check if all the cells in the column (in the left of it) and row (above it) are 1 or not (Boundary being the row and column value of current cell being considered). If all cells are not 1s, we have found the maximum square and return. But if all cells have value 1, we go on to next diagonal LEFT-DOWN cell and repeat the process.
• Finally return the maximum size found.

Implementation

Complexity

We repeat the exploration process for each cell. There are $mn$ number of cells in the given matrix and the exploration of each cell can take $O(mn)$ time.$\therefore$ Total time complexity of this method $O((mn)^2)$.

As for space, it does not use any extra data structure. So its space complexity is $O(1)$

Solution 2: Dynamic Programming Solution

If the currently considered cell has a value 1, the minimum size of the square it can form is 1. To find the maximum size, we need to look into its neighbor cells at RIGHT, DOWN and RIGHT-DOWN (Assuming currently considered cell is the TOP-LEFT corner of the square)

If all the three neighbors are square of size 1, then the current cell will form square of size 2.

If any one of the three neighbors is square of size 0, then the currently considered cell can form square of size 1 only.

What will be the maximum size square if the neighbors are the square of size greater than 1.

In the example above:

1. Right Neighbor forms square of size 3
2. Right-Down Neighbor forms square of size 4
3. Down Neighbor forms square of size 2

From the figure, it is obvious that the square formed by current cell is 3.

Can we compute this value from the neighbor values? YES!! The value can be computed from neighbors as follows:

size of square that current cell can form = 1 + Minimum(size of neighbors)

Base Case

Since the bottom Row and right most column don't have cells to form square, number in them, either 0 or 1 is the maximum size of the square they can form.

Implementation

Since we will be using each of the cell as the TOP-LEFT corner of the square they can form, we can start the computation from the RIGHT BOTTOM because their value will not depend upon the values above them or left to them. We can then move towards left or up.

For this implementation we will need to maintain Auxiliary Matrix of the same size as the input matrix to hold the sizes of the square that each cell can form.

Complexity

With this method, we will be traversing through each of the cells only once. For the computation of current cell, we need to access at max three other cell values. So, the Time Complexity of this method is $O(mn)$.

As for space, we are using extra matrix of same size as an input. Thus the space complexity is also $O(mn)$.

Solution 3: Better Dynamic Programming Solution, O(n) Extra Space

In the previous implementation, we can see that we are using the Auxiliary Matrix to access only 3 of previous values to compute value for current cell. Hence, we don't need the whole matrix all the time. It is sufficient to store the result of one row at a time.For every row, when we traverse from right to left, the Auxiliary Array is also updated from right to left.

if size[] be the auxiliary array,

For any cell matrix[r][c],

size[c+1] represents Right Neighbor
size[c] represents Down Neighbor, and
prev (previous value of size[c]) represents Diagonal Neighbor

---

---

---