Get indexes of unique elements in two different arrays in linear time

Question

I have two array of the same set of elements, say for exemple: $a_1 = [x_1, x_2, …, x_n]$ and $a_2 = [y_1, y_2, …, y_n]$ so that $i \neq j \Rightarrow x_i \neq x_j$

Is it possible, in linear time, to construct the array $[(x_1, k_1), (x_2, k_2), …, (x_n, k_n)]$ so that $y_{k_i} = x_i$ ?

I found that with dictionnaries, I can get $O(n)$ in average and $O(n^2)$ in worst (hashtable) or $O(n\log n)$ in average and worst (balancing trees), but can't find a way to make it $O(n)$ in worst case.

We can suppose that the $x_i$ objects are integers, since it could represent memory pointers.

I found that it is possible if the set is $[\![1, n]\!]$ (just construct the array directly).

Thanks for your help.

Answer 1

Given the following assumptions:

1. Since the meaning of the $=$ operator was not defined, we assume

$i≠j⇒x_i≠x_j$

...

The $x_i$ values are not necessarily integers or string, but any type of elements.

are taken to mean that each element of the set simply has a different encoding i.e. is represented by a different number in memory, and that each element is a single word, perhaps a distinct pointer to some arbitrary object.

2. We assume that, given an arbitrary address, reading/writing at that address takes constant time.

3. We assume that adding 2 addresses takes constant time.

4. We assume that a pointer to unbounded memory is available in n time.

Assumptions 2 through 3 hold in most modern system, up to the memory capacity of the system. 4 only considers this program's logical space.

Then:

Consider the following construction (pseudocode). Note the time complexity, marked by "--":

//Arrays are indexed starting at 1.
//"*x = y" denotes "store y at the address pointed to by x"
//"x = *y" denotes "store the value, at the address pointed to by y, to x"

//Given:
input a1        //pointer to array a1
input a2        //pointer to array a2
input n         //number of elements in set
input mem       //address of unbounded hash table
                  //in the sense of a multitape Turing Machine, 
                  //this points to the first address on "another tape"
output result   //address of n-length array of Tuples

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    hashkey = mem + a2[t] //find an address for this element; is unique
                          //since each element is unique
    *hashkey = t;         //store the index $k_i$ at this address
}

//mem is now a pointer to a (collision free) hash table

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    k = *(a1[t])
    *(result[t]) = Tuple(a1[t], k)
}

return result

...yes this dodges the question by using the suspicious "unbounded hash table". We could be pedantic and argue that the hash table is not technically unbounded on any system we might use, but by this same pedantry we can argue that the lower time complexity bounds of every non-trivial parameterized problem is $O(∞)$ just because we can choose parameters that happen to be too large for the system's address space.

The time complexity of the algorithm, address space permitting, is thus bounded by $T(2n) ∈ O(n)$.

Answer 2

For the record, here is an $\Omega(n^2)$ lower bound when your only access to the data is using queries of the form "$x_i = y_j$?". The proof uses an adversary argument. We will assume for convenience that $n$ is divisible by $8$.

We will maintain a bipartite graph, initially with $n$ nodes on each side, corresponding to $x_1,\ldots,x_n$ on one side and to $y_1,\ldots,y_n$ on the other. There is an edge connecting $x_i$ to $y_j$ if the algorithm hasn't found out that $x_i$ is different from $y_j$. Initially, the graph is complete. If we answer a query of the algorithm by $x_i \neq y_j$ (we will soon discuss our answering strategy), then we simply remove the edge $(x_i,y_j)$. If we answer a query by $x_i = y_j$, then we remove the vertices $x_i,y_j$.

Our answering strategy will always maintain the invariant that the current bipartite graph always contains at least two perfect matchings, and so the algorithm cannot tell how to match the $x$'s with the $y$'s. We will guarantee that by ensuring that all vertices have degree at least $n/2+1$. Let us explain why this guarantees the existence of at least two perfect matchings.

First, let us show that if all vertices have degree at least $n/2$ then there is at least one perfect matching. According to Hall's theorem, there is a perfect matching if every set $S$ on the left-hand side has at least $|S|$ neighbors on the right-hand side. This is clearly satisfied when $|S| \leq n/2$. If $|S| > n/2$ then every vertex on the right-hand side is a neighbor of $S$, since otherwise it will have degree less than $n/2$.

Suppose now that all vertices have degree at least $n/2+1$. Take any vertex $v$ on the left. If we choose any of its neighbors $u$ on the right and remove both, then the remaining graph still has minimum degree at least $n/2$. Hence there is a perfect matching in which $v$ is matched to $u$. Since $v$ has at least two neighbors, this shows that there are at least two different perfect matchings.

We now describe our answering strategy. The strategy proceeds in phases, starting with phase $0$. We move to next phase after each time we answer a query by $x_i = y_j$. We will maintain the invariant that in phase $t$, all vertices have degree at least $(3/4)n-t$. This implies that all vertices have degree at least $n/2+1$ as long as $t < n/4$.

Suppose that the algorithm asks "$x_i = y_j$?" during phase $t$. If both $x_i$ and $y_j$ have degree larger than $(3/4)n-t$, then we answer $x_i \neq y_j$. This clearly maintains the invariant. If one of them has degree exactly $(3/4)n-t$, then we answer $x_i = y_j$, and proceed to phase $t+1$. This also maintains the invariant, since we have decreased each degree by at most $1$.

As we have shown above, the algorithm cannot stop until reaching phase $n/4$, since in every earlier phase there are at least two perfect matchings consistent with the known information. It remains to lower bound the number of queries needed to reach phase $n/4$. We will actually lower bound the number of queries needed to reach phase $n/8$. In order to reach phase $t$ from phase $t-1$, the degree of some vertex $v_t$ must reach $(3/4)n-t \leq (3/4)n$. So in order to reach phase $n/8$, the degree of $n/8$ vertices $v_1,\ldots,v_{n/8}$ needs to reach $(3/4)n$ or below.

The degree of a vertex can be decreased in two ways. When the algorithm answers $x_i = y_j$, the degrees of the neighbors of $x_i,y_j$ decrease by $1$; let us call this a major decrease. When the algorithm answers $x_i \neq y_j$, the degrees of $x_i,y_j$ decreases by $1$; let us call this a minor decrease. Since there are $n/8$ major decreases up to phase $n/8$, they can reduce the degree of $v_1,\ldots,v_{n/8}$ by at most $n/8$ each. Each of these vertices has to have its degree reduced using minor decreases by at least $n/8$. Since each minor decrease affects two vertices, there must be at least $(n/8)^2/2 = \Omega(n^2)$ minor decreases. In other words, the algorithm must make at least $\Omega(n^2)$ many queries.

Conversely, the problem can be solved using $\binom{n}{2} \leq n^2/2$ queries, by finding the correct match for the vertices on the left side one by one. Is this algorithm optimal? This is an interesting question for future work.