Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries

Philip Bille, Johannes Fischer, Inge Li Gørtz +1

We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $\sigma$ to answer \textsc{All-Distinct} que…