Python Program to Find the Largest Square Containing Only 1s in a Binary Matrix

Problem Statement

Given a binary matrix (a matrix with only 0s and 1s), the task is to find the largest square that contains only 1s. We need to return the size of the largest square.

Approach Explanation

The idea is to use dynamic programming to solve this problem efficiently. We will create a DP table (a 2D list) where each entry at position (i, j) contains the size of the largest square submatrix whose bottom-right corner is at (i, j).

Dynamic Programming Transition:

• If the element in the original matrix is 0, the corresponding element in the DP table will also be 0 (as it cannot contribute to any square of 1s).
• If the element in the original matrix is 1, we check the minimum value among the three adjacent cells (left, top, top-left) in the DP table and add 1 to it. This gives us the size of the largest square ending at (i, j).

Time Complexity:

O(m * n) where m is the number of rows and n is the number of columns in the matrix.

Space Complexity:

O(m * n) for the DP table.

Python Code

def maximalSquare(matrix):
    """
    Function to find the size of the largest square containing only 1s in a binary matrix.
    
    Args:
    matrix (List[List[int]]): 2D binary matrix containing 0s and 1s.
    
    Returns:
    int: The area of the largest square of 1s.
    """
    if not matrix or not matrix[0]:
        return 0

    # Get dimensions of the matrix
    rows = len(matrix)
    cols = len(matrix[0])

    # Initialize a DP array with the same size as the input matrix
    dp = [[0] * cols for _ in range(rows)]
    max_square_length = 0

    # Traverse the matrix
    for i in range(rows):
        for j in range(cols):
            # If the current element is '1'
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    # For the first row or first column, the largest square is 1
                    dp[i][j] = 1
                else:
                    # Calculate the minimum of the three neighboring squares
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                
                # Keep track of the maximum square length
                max_square_length = max(max_square_length, dp[i][j])

    # Return the area of the largest square
    return max_square_length ** 2


# Example Usage
binary_matrix = [
    ['1', '0', '1', '0', '0'],
    ['1', '0', '1', '1', '1'],
    ['1', '1', '1', '1', '1'],
    ['1', '0', '0', '1', '0']
]

print("Largest square area is:", maximalSquare(binary_matrix))
    

Explanation of the Program

Let’s break down the structure of the program:

1. Input:

The input is a binary matrix where each element is either ‘1’ or ‘0’. For example:

    [
        ['1', '0', '1', '0', '0'],
        ['1', '0', '1', '1', '1'],
        ['1', '1', '1', '1', '1'],
        ['1', '0', '0', '1', '0']
    ]

2. DP Table Initialization:

A DP table (2D list) is created, initialized with zeros. This table is used to store the size of the largest square ending at each position in the matrix.

3. Iteration Over the Matrix:

The program iterates over the entire matrix. For each ‘1’ in the matrix, it computes the size of the largest square submatrix ending at that position. It does so by checking the minimum value among the left, top, and top-left neighbors in the DP table and adding 1.

4. Maximum Square Length:

The variable max_square_length keeps track of the largest square’s size as we process the matrix. Once the iteration is complete, we return the area of the square by squaring the largest side length.

5. Example Execution:

For the provided matrix, the largest square of 1s has an area of 4 (2×2 square).

Output:

For the given input, the program will output:

Largest square area is: 4