221. Maximal Square

Problem Statement

link: https://leetcode.com/problems/maximal-square/ https://leetcode.cn/problems/maximal-square/

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

Example:

Input: ` matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]] **Output:** 4`

Input: matrix = [["0","1"],["1","0"]] Output: 1

Input: matrix = [["0"]] Output: 0

Solution Approach

The problem is solved using dynamic programming. We iterate through the given binary matrix, maintaining a 2D array to track the largest square ending at each position. The final answer is the square of the maximum value in this 2D array.

Algorithm

1. Dynamic Programming: Use dynamic programming to compute the side length of squares ending at each position.
2. Square Expansion Logic: For each ‘1’ in the matrix, calculate the square’s side length by taking the minimum of adjacent squares and incrementing it by 1.
3. Maximal Square Area: Maintain ‘res’ as the maximum side length encountered and return ‘res’ squared as the largest square area.

Implement

    # m n  # dp[i][j] = min dp[i-1][j-1],dp[i-1][j],dp[i][j-1] + 1 if matrix[i][j] == 1 else 0 class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        if n == 0:
            return 0
        res = 0
        dp1 = [0] * (n + 1)
        dp2 = [0] * (n + 1)
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == "1":
                    dp2[j] = min(dp1[j - 1], dp1[j], dp2[j - 1]) + 1
                    res = max(res, dp2[j])
                else:
                    dp2[j] = 0
            dp1 = dp2[:]
        return res * res
        
  

    
    

Twitter  facebook  Email