1
$\begingroup$

The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to solve it, e.g. via a hashmap or binary tree. Luckily, I have an untrustworthy but omnipotent oracle ally who is willing to give me hints on how to solve the problem.

The oracle is allowed to provide me $O(n)$ of hints, and I want an algorithm that will read $A$ and the oracle input (both read only) and determine either that $A$ has no duplicates, or that the oracle has given me a bad hint, in time $O(n)$ and much smaller read-write space ($O(1)$ or $O(\log n)$).

Can it be done?

$\endgroup$
  • $\begingroup$ How large are your elements? Do you count space in bits or words? $\endgroup$ – Yuval Filmus Aug 21 at 7:46
  • $\begingroup$ @YuvalFilmus Sorry for not specifying; I am indeed using a RAM machine model, so words are fine. $\endgroup$ – Mario Carneiro Aug 22 at 8:19
2
$\begingroup$

You haven't specified your exact computation model, so let me assume that you measure space in words of length $\Theta(\log n)$, and that each element in the array occupies one word. Let me assume furthermore that you can compare two elements in constant time.

The oracle should provide you with the relative order of the elements, say as an array $B$ whose entries are the numbers $1,\ldots,n$ in the appropriate order. This advice takes $O(n)$ words, and can be verified in $O(n)$ time and $O(1)$ additional space.

In slightly more detail, here is the verification algorithm:

for i from 1 to n:
  verify that 1 ≤ B[i] ≤ n
for i from 2 to n:
  verify that A[B[i-1]] < A[B[i]]

Let us prove that there exists an array $B$ for which the verification succeeds iff $A$ consists of distinct elements.

$\longleftarrow$ Suppose that $A$ consists of distinct elements. Order $A$ in increasing order: $A[j_1] < \cdots < A[j_n]$. If we take $B[i] = j_i$ then the verification will succeed.

$\longrightarrow$ Suppose that the verification succeeds for some array $B$. Then $A[B[1]] < \cdots < A[B[n]]$. This implies that $A$ contains at least (and so exactly) $n$ distinct elements.

$\endgroup$
  • $\begingroup$ How do you know that the numbers 1 through n all appear exactly once in $B$? I assume that the verification you envision is the traversal $A[B(i)]$ as $i$ goes from 1 to n, which makes the order checking of $A$ easy but it's possible that $B$ skips an element or visits the same element twice. $\endgroup$ – Mario Carneiro Aug 22 at 8:25
  • $\begingroup$ One follow up observation: If the elements of $A$ are strings, say, with variable length (where $n$ now means the total size of $A$, i.e. the sum of the lengths), then we can still use this scheme, but we need an additional table $C$ that can be provided as advice, which provides $|A|$ pointers to the elements of $A$ in order (which can be verified in one pass through $A$ and $C$), and then $B$ uses indexes into $C$. $\endgroup$ – Mario Carneiro Aug 22 at 8:33
  • $\begingroup$ Regarding your second comment, it is hard to answer a moving target. I will assume that the elements of $A$ fit into a single word. $\endgroup$ – Yuval Filmus Aug 22 at 8:36
  • $\begingroup$ You don't need to verify that all numbers in $B$ are distinct. The only way to have $n$ strictly increasing values is if all of them are distinct. $\endgroup$ – Yuval Filmus Aug 22 at 8:37
  • $\begingroup$ No worries, you've answered the given question. I just wanted to point out that this also solves the variable length version of the problem. $\endgroup$ – Mario Carneiro Aug 22 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.