arXiv preprint ·
Many Scores Force Many Reads: An Optimality Proof for Score of Parentheses
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
LeetCode Problem 856, Score of Parentheses, admits a one-pass algorithm using $O(n)$ time and $O(1)$ auxiliary registers. Its correctness follows from a local interpretation: every occurrence of () contributes a power of two determined by its nesting depth. The space bound is immediately optimal in the usual programming-challenge model, but the linear-time bound is less obvious. In particular, a direct adversary that forces an algorithm to inspect every character is difficult to maintain under the promise that the input is balanced. We instead prove a counting lower bound. For every $k$, we construct $2^k$ balanced parenthesis strings of the same length $4k+2$, all having distinct scores. The construction encodes each bit using one of two operations, changing a current score $v$ to either $2v+1$ or $2v+2$. Consequently, any deterministic character-query decision tree computing the score must have depth at least $k$. A two-character padding argument extends the result to every even input length, proving an $Ω(n)$ worst-case time lower bound. The one-pass algorithm is therefore asymptotically optimal in the unit-cost RAM model.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
Faster Deterministic Approximation for Counting Knapsack
Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching
The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation
Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.