<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>

'''
Idea: prefix count

(1, 4), (0, 0), (1, 3), (0, 0), (0, 0)
(1, 3), (0, 0), (3, 2), (2, 2), (1, 2)
(5, 2), (4, 1), (3, 1), (2, 2), (1, 1)
(1, 1), (0, 0), (0, 0), (1, 1), (0, 0)

Idea: binary search
- Time: O(log(L)*m*n)
    - L = min(m, n)
- Space: O(mn)
'''
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        num_rows, num_cols = len(matrix), len(matrix[0])
        def square_exists(square_len):
            for row in range(num_rows):
                for col in range(num_cols):
                    if is_square_with_len(row, col, square_len):
                        return True
            return False

        runlen = [[[0, 0] for _ in range(num_cols)] for _ in range(num_rows)]
        for row in range(num_rows-1, -1, -1):
            for col in range(num_cols-1, -1, -1):
                if matrix[row][col] == '1':
                    runlen[row][col][0] = 1
                    if row < num_rows-1:
                        runlen[row][col][0] += runlen[row+1][col][0]
                    runlen[row][col][1] = 1
                    if col < num_cols-1:
                        runlen[row][col][1] += runlen[row][col+1][1]

        print(runlen)
        def is_square_with_len(row_start, col_start, square_len):
            if row_start+square_len > num_rows:
                return False
            if col_start+square_len > num_cols:
                return False
            while square_len:
                row_run, col_run = runlen[row_start][col_start]
                if row_run < square_len or col_run < square_len:
                    return False
                row_start += 1
                col_start += 1
                square_len -= 1
            return True

        # def is_square_with_len(row_start, col_start, square_len):
        #     if row_start+square_len > num_rows:
        #         return False
        #     if col_start+square_len > num_cols:
        #         return False
        #     for row in range(row_start, row_start+square_len):
        #         for col in range(col_start, col_start+square_len):
        #             if matrix[row][col] != '1':
        #                 return False
        #     return True

        # loop invariant: lo points to a valid square length
        lo, hi = 0, min(num_rows, num_cols)+1
        while lo < hi:
            mid = (lo + hi + 1) >> 1
            if square_exists(mid):
                lo = mid
            else:
                hi = mid - 1
        return hi*hi
28925