<p>Given an <code>m x n</code> binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, <em>find the largest square containing only</em> <code>1</code>&#39;s <em>and return its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg" style="width: 400px; height: 319px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg" style="width: 165px; height: 165px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;]]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>matrix[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # returns area of largest square of ones
        # naive: we could go through all lengths and check if square exists of that lengtn
        # can binary search it due to monolicity
        # 0 -> n
        # for each possible side len, loop all squares but also sum up all boxes in square? kinda slow. n*n*i*i
        # square is good if sum inside is i*i, can easily get that with prefix summing
        # finally, bounds of loop for i: i=side_len-1 -> end j= side_len-1 -> end
        n,m = len(matrix), len(matrix[0])
        if not n and not m:
            return 0
        prefix_sums = {} # use subproblem
        prefix_sums[(0,0)] = int(matrix[0][0])
        prefix_sums[(-1,-1)] = 0
        prefix_sums[(0,-1)] = 0
        prefix_sums[(-1,0)] = 0
        for c in range(1, m):
            prefix_sums[(0,c)] = prefix_sums[(0,c-1)]+int(matrix[0][c])
            prefix_sums[(-1,c)] = 0
        for r in range(1,n):
            prefix_sums[(r,0)] = prefix_sums[(r-1,0)]+int(matrix[r][0])
            prefix_sums[(r,-1)] = 0
        for i in range(1,n):
            for j in range(1,m):
                prefix_sums[(i,j)] = prefix_sums[(i-1,j)]+prefix_sums[(i,j-1)]-prefix_sums[(i-1,j-1)]+int(matrix[i][j])
        def is_filled_with_ones(i,j,side_len):
            #print(i,j,side_len)
            #print(prefix_sums)
            # if (i,j) == (2,4):
                #print(f"sum at 2,3 {prefix_sums[(i,j)]-prefix_sums[(i-side_len,j)]-prefix_sums[(i,j-side_len)]+prefix_sums[(i-side_len,j-side_len)]}")
            return (prefix_sums[(i,j)]-prefix_sums[(i-side_len,j)]-prefix_sums[(i,j-side_len)]+prefix_sums[(i-side_len,j-side_len)]) == (side_len * side_len)
        def condition(side_len):
            for i in range(side_len-1, n):
                for j in range(side_len-1, m):
                    if is_filled_with_ones(i,j,side_len):
                        return True
            return False # is not exist 11-2-7=2+2 = 4
        l, r = 0, min(n,m)
        while l < r:
            mid = (l+r+1)//2
            #print("m is condition is ", mid, condition(mid))
            if condition(mid): # if exist
                l = mid
            else: # exitisth
                r = mid-1
        return l*l
        
37175