Maximal Square - Leetcode Solution

The Maximal Square problem on LeetCode is a dynamic programming problem that asks you to find the area of the largest square formed in a 2D binary matrix (a matrix consisting of only 0's and 1's).

To solve this problem, we will use dynamic programming. We will create a 2D array where each element (i, j) represents the size of the largest square that can be formed using the bottom right corner of the (i, j) element. We will fill this array by iterating over the matrix and calculating the size of the largest square each (i, j) element can form by considering the (i-1, j), (i-1, j-1), and (i, j-1) elements.

Let's look at the steps in detail:

Step 1: Initialize a 2D array with the same size as the input matrix, and fill the first row and first column with the corresponding values of the input matrix.

Step 2: Traverse through the remaining elements of the array. If the current element in the input matrix is 1, then calculate the maximum size of the square that can be formed using the current element as the bottom right corner, and update the 2D array.

To calculate the maximum size of the square, we check the values of its three adjacent elements in the 2D array (top, diagonal, left). The largest square that can be formed in this position will be 1 + the minimum size of the square that can be formed using these three elements.

At each iteration, we keep track of the maximum size of the squares calculated so far.

Step 3: Return the area of the largest square calculated.

Here is a sample implementation in Python:

def maximalSquare(matrix):
    """
    :type matrix: List[List[str]]
    :rtype: int
    """
    if not matrix:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    dp_table = [[0]*n for _ in range(m)]
    max_area = 0
    
    # fill first row and col
    for i in range(m):
        dp_table[i][0] = int(matrix[i][0])
        max_area = max(max_area, dp_table[i][0])
    for j in range(n):
        dp_table[0][j] = int(matrix[0][j])
        max_area = max(max_area, dp_table[0][j])
    
    # fill rest of the matrix
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == '1':
                dp_table[i][j] = 1 + min(dp_table[i-1][j], dp_table[i][j-1], dp_table[i-1][j-1])
                max_area = max(max_area, dp_table[i][j]**2)
    
    return max_area

Time Complexity: O(mn) Space Complexity: O(mn)

1