6 papers
Many Scores Force Many Reads: An Optimality Proof for Score of Parentheses
Andrew Au
LeetCode Problem 856, Score of Parentheses, admits a one-pass algorithm using time and auxiliary registers. Its correctness follows from a local interpretation: every…
A Geometric Derivation of the Bitner--Ehrlich--Reingold Loopless Gray Code Algorithm
Andrew Au
The Bitner--Ehrlich--Reingold algorithm generates the binary reflected Gray code with constant work per codeword, using a focus-pointer array. Its compact update is easy to state b…
Do We Really Need to Read the Input? An Optimality Proof for Stone Game III
Andrew Au
Stone Game III admits a standard backward dynamic program using time and auxiliary space. The upper bound is immediate, but its optimality raises a deceptively simple…
A Tight Lower Bound for Cycle Detection in Grid Graphs
Andrew Au
We prove that any algorithm for detecting cycles in an grid graph, where cells are colored and adjacency is defined by matching colors, must read all cells in the…
Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space
Andrew Au
We prove that any algorithm computing the sum-exclude-self of an unsigned -bit integer array of length under sublinear space must perform two linear passes over the input. M…
Exact (n + 1) Comparison Complexity for the N-Repeated Element Problem
Andrew Au
This paper establishes the exact comparison complexity of finding an element repeated times in a -element array containing distinct values, under the equality-compari…