Question

Formatted question description: https://leetcode.ca/all/221.html

 221	Maximal Square

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

For example, given the following matrix:

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

Return 4.

----- Test Case -----
Input: [["1"]]
Expected: 1

Input: [["0"]]
Expected: 0

@tag-dp


Algorithm

The brute force method, mechanism of this method is to treat each point in the array as the left vertex of a square and scan to the bottom right to find the largest square.

But, there is better solution.

After establishing the cumulative sum array, we start to traverse every position of the two-dimensional array. For any position (i, j), we traverse all squares from that position to (0,0), the number of squares is min(i,j)+1,

Because of the cumulative sum matrix, we can quickly find the sum of any area, so we can quickly get the sum of all sub-squares,

Compare whether the sum of the square is equal to the square of the side length. The equality means that the numbers in the square are all 1. Then update the result.

Java