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

Abstract

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} queries, asking whether a given range contains only distinct elements. We first focus on \emph{uniformly random arrays}: in the encoding model, where access to the input at query time is not allowed, we prove a lower bound on the expected space; for instance, the lower bound is $n$, $1.3627n$, $1.5153n$, $1.5824n$ bits for $\sigma =2,3,4,5$, and approximately $n\sqrt{\pi /(2\sigma )}\log \sigma$ bits for $\sigma =\omega (1)$. We complement this by designing different average-case optimal encodings, supporting \textsc{All-Distinct} queries in worst-case time $O(1)$, $o({\log }^2\log n)$, or $O(\log \log n)$ depending on $\sigma$, and $O(1)$ expected time for any $\sigma =\omega (1)$. We then switch to worst-case (non-random) arrays: in the indexing model, where access to the input is allowed, we prove a cell-probe space-time tradeoff lower bound showing that any index using $n/b$ bits must have $\Omega (b/\log b)$ query time. We conclude by presenting a simple index almost matching this lower bound.

Accepted at SPIRE 2026. Full version