= Solution
For the flattened Boolean <array>, the <abstraction function> selects the true cells. A suitable <representation invariant> requires the occupied cells to form a <order ideal>: an occupied $(x,y)$ implies occupancy of every $(i,j)$ with $i\leq x,j\leq y$. Deleting a northeast rectangle preserves that property.
For column heights, the invariant is $N\geq h(0)\geq h(1)\geq\cdots\geq h(N-1)\geq0$, and the <abstraction function> is $B=\{(x,y):0\leq x<N,\ 0\leq y<h(x)\}$. A legal move replaces every $h(i)$ for $i\geq x$ by $\min(h(i),y)$, preserving the invariant. This is an <order-ideal board representation>.
For a fair comparison, allow either representation a scalar cached token count: `Count` and `Legal` then take $O(1)$ in both. Without that cache, counting needs $\Theta(N^2)$ Boolean inspections versus $\Theta(N)$ height additions. A move takes $O(N^2)$ in the worst case in the flattened representation and $O(N)$ with heights. Displaying the full square takes $\Theta(N^2)$ character positions in either. Heights use \b[$\Theta(N)$ <array> entries rather than $\Theta(N^2)$], so they are superior for the requested operations; their initialization also takes only $\Theta(N)$ time.
Back to article page
