  We present the first linear time algorithm to construct the $2n$-bit version
of the Lyndon array for a string of length $n$ using only $o(n)$ bits of
working space. A simpler variant of this algorithm computes the plain ($n\lg
n$-bit) version of the Lyndon array using only $\mathcal{O}(1)$ words of
additional working space. All previous algorithms are either not linear, or use
at least $n\lg n$ bits of additional working space. Also in practice, our new
algorithms outperform the previous best ones by an order of magnitude, both in
terms of time and space.
