= Solution
Fix the top-right corner $(i,j)$ and a bottom boundary $k$. A width $w$ is feasible precisely when every row $m\in[i,k)$ has at least $w$ consecutive true entries ending at column $j$. Thus the largest feasible width is the minimum of those <row run lengths>, and the area is that width times $k-i$.
``
def maxRectangleAt(i: Int, j: Int): Int = {
var k = i
var width = j + 1
var best = 0
while (k < N) {
width = math.min(width, rowCount(k)(j))
k += 1
best = math.max(best, (k - i) * width)
}
best
}
``
At the loop head, the <loop invariant> is $i\leq k\leq N$,
$$
\begin{aligned}
\mathrm{width}&=\min\bigl(\{j+1\}\cup\{\mathrm{rowCount}(m)(j):i\leq m<k\}\bigr),\\
\mathrm{best}&=\max\bigl(\{0\}\cup\{(h-i)\min_{i\leq m<h}\mathrm{rowCount}(m)(j):i<h\leq k\}\bigr).
\end{aligned}
$$
The initial cap $j+1$ makes the empty-prefix case well-defined and cannot restrict any actual run. Each iteration incorporates one new row and tests its corresponding bottom boundary. The <loop variant> is $N-k$, so
$$
\boxed{\mathrm{best}=\max_{i<k\leq N}(k-i)\min_{i\leq m<k}\mathrm{rowCount}(m)(j),\qquad O(N).}
$$
A zero width contributes area zero, covering the case where no nonempty all-true <rectangle> starts at that corner.
Back to article page
