[leetcode] Maximal Square


Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

For example, given the following matrix:

Return 4.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Dynamic programming, dp[i][j] stores the maximum side length of square whose bottom-right coordinate is (i, j)

dp[i][0] = matrix[i][0] – ‘0’

dp[0][i] = matrix[0][i] – ‘0’

dp[i][j] = 0 if matrix[i][j] == 0

dp[i][j] = 1 + min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1])

 

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
Notify of