algoadvance

Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

You can assume that matrix is a binary matrix (contains only 0 and 1) and the number of rows and columns does not exceed 300.

Clarifying Questions

1. Q: Are there any restrictions on the values within the matrix?
   • A: The matrix contains only binary values, ‘0’ and ‘1’.
2. Q: What should be returned if the matrix is empty?
   • A: If the matrix is empty, the function should return 0.
3. Q: What are the dimensions of the matrix?
   • A: The number of rows and columns does not exceed 300.

Strategy

To solve this problem, we can use dynamic programming. The idea is to maintain a 2D DP array where dp[i][j] represents the side length of the largest square whose bottom-right corner is at matrix[i][j].

1. Initialize a DP array with the same dimensions as the matrix filled with zeroes.
2. Iterate through each cell in the matrix:
   • If the cell contains ‘1’, update the DP array at that position. The value of dp[i][j] will be the minimum of the three possible neighboring values (left, top, and top-left) plus one.
3. Track the maximum length of the square found during the iteration.
4. The area of the largest square will be the square of this maximum length.

Example

For a given matrix:

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

The largest square containing only 1’s has an area of 4 (2x2 square).

Code

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    dp = [[0] * cols for _ in range(rows)]
    max_side = 0
    
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                max_side = max(max_side, dp[i][j])
    
    return max_side * max_side

# Example usage:
matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]
print(maximalSquare(matrix))  # Output: 4

Time Complexity

• Time Complexity: (O(m \times n)) where m is the number of rows and n is the number of columns of the matrix. This is because we iterate through each cell once.
• Space Complexity: (O(m \times n)) for the DP array. However, if we optimize and use a single row array, the space complexity can be reduced to (O(n)).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?