Maximal Square

1. How to approach this problem?

Let us simplify our approach by only considering the largest square at a position where the position represents the bottom right corner of our square

1. Identifying a Pattern

If you know the largest square you can create around a given position in the matrix, what allows us to say we can create a valid subsquare at that position.

Algorithm

Naive Implementation

The most straightforward solution would be to try every single possible size that our square could be and then scan our matrix if a subsquare of that size is in our matrix. In the worst case, this yields a runtime of $O((nm)^2)$ because in the worst case, we will traverse the matrix in its entirety $nm$ times.

Using Dynammic Programming

Instead, we can consider a dynamic programming approach to this problem. Let us initialize an n by m matrix with the same dimensions as mat. We can let each entry of the matrix represent the side length of the largest subsquare whose bottom right corner is the current entry. Now, notice the value of an entry depends on the values of the squares immediate above, left, and right of it. More specifically, if corresponding entry in mat is a 1, then the largest subsquare we can create is 1 plus the minimum of the largest subsquare we can create with the entries above, right, and left of the entry.

Finally, to reduce our space complexity, since each entry only depends on the values of a single row at a time, we only need to keep track of a two rows at a time rather than the entire matrix.

Code

def maximal_square(mat):
    """
    input mat: a binary matrix
    output: an integer representing the dimensions of the largest square matrix of mat
    """
    if rows == 0:
        return 0
    rows = len(matrix)
    cols = len(matrix[0])
    
    # Initialize our bottom-up dp matrix where dp[0] is the previous row and
    # dp[1] is the current row
    dp = [[0 for i in range(cols)] for j in range(2)]
    d = 0
    
    for row in range(rows):
        for col in range(cols):
            # Base case - if we're at the left or top of matrix
            if row == 0 or col == 0:
                dp[1][col] = mat[row][col]
            else:
                # If the current entry has a 1, find the largest possible square
                # given the largest possible squares of the squares around it
                if mat[row][col] == 1:
                    dp[1][col] = 1 + min(dp[0][col], dp[1][col - 1], dp[0][col - 1])
                else:
                    dp[1][col] = 0
            # Update the largest square we're found so far    
            d = max(d, dp[1][col])
        # Move dp[1], our current row, to dp[0] the prev row
        dp[0], dp[1] = dp[1], dp[0]
    return d
    

Example

Below is an example of the full dp matrix (Note: in our implementation we only keep track of 2 rows at a time). Again, notice how every square is 1 plus the minimum of its upper left neighbors.

Input: 
1 0 1 0 0 1
1 1 1 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1

DP:
1 0 1 0 0 1
1 1 1 1 1 1
1 2 2 0 1 2
1 2 3 1 0 1

Runtime Analysis

The runtime of this algorithm is $O(nm)$ since we iterate through the matrix once.

Space Complexity

Our space complexity is $O(n)$ since we are only keeping track of a constant number of rows at a time.

Solution for the Follow-up Question

We want to use the same concept as we did for original problem, but extended to 3 dimensions. Instead of storing the largest square we can make using that square as the bottom right square, we’ll instead store the largest cube we can create given that the entry is the bottom right corner closest to us. In addition to that we also need to consider not only the squares above and left of us, we also need to minimize over the square behind the entry. We need to tweak 3 things to our original solution for it to work in 3 dimensions. First, we need to adjust the base case to account for 3 dimensions. Second, we need to allow our dp matrix to hold planes, or 2-dimensional matrices, at a time rather than just rows. Finally, we need to alter our min function to include one extra dimension.