6
$\begingroup$

I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.

Given two arrays $a$ and $b$ which contain the same set of distinct integers, determine for every element of $a$ the index of the same element in $b$.

For example, if $a=[9,4,3,7]$ and $b=[3,4,7,9]$, then the output should be $[3,1,0,2]$.

Note that this becomes a very easy task when you have a hashset, because you can simply store for every element in $b$ the index, and then query the hashmap for every element of $a$.

So my question is whether there is a linear algorithm for this task that does not use any hashsets.

$\endgroup$
3
$\begingroup$

If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $\Theta(n\log n)$ time in worst case for any algorithm.

This can be seen from the situation when array $a$ is sorted while array $b$ is arbitrary before we apply the algorithm. Knowing the index $I(k)$ of the element in $b$ which is the same as the $k$-th element of $a$ for all $k$, we can sort $b$ in $O(n)$ time by simply putting $b_{I(k)}$ in $k$-th position (using one temporary working space or a new result array of length $n$). However, it is well-known that it takes at least $\Theta(n\log n)$ time (comparisons) to sort $b$ in worst cases for any algorithm. So obtaining that knowledge, the index $I(k)$ for all $k$ must take at least $$\Theta(n\log n)- O(n)=\Theta(n\log n)$$ time as well in worst cases.

The following is a formal formulation of the conclusion above in the comparison computation model.

Let $\mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,f\in E$, $\mathcal O$ outputs -1 if $e\prec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from $\{0, 1,\cdots, n-1\}$ to $E$. To output $I(0), I(1), \cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0\le k\le n-1$, it will take $\Theta(n\log n)$ queries against $\mathcal O$ in the worst case.

whether there is a linear algorithm for this task that does not use any hashsets.

A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.

$\endgroup$
  • $\begingroup$ I don't think OP is asking for an ordering of the elements of a. It sounds more like he is asking for a mapping i.e. map element of a to it's position in b; not order elements of a according to their position in b. Ordering will require O(nlogn) as you have astutely observed, but mapping can be done in O(n). $\endgroup$ – smac89 Mar 20 at 3:53
  • $\begingroup$ Exactly, I don't think OP is asking for an ordering of the element of $a$. Please read my answer carefully, especially the formal formulation. Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat. $\endgroup$ – Apass.Jack Mar 20 at 3:59
  • $\begingroup$ This answer abstracts "distinct integers" as "distinct elements" with a strict total order. There could be other computation models for "distinct integers" without "hashset". $\endgroup$ – Apass.Jack Mar 20 at 4:47
  • $\begingroup$ Very interesting answer! Thank you! One question, though: You claim such a linear algorithm allows linear sorting. If I understand your argument correctly it goes like this. You can simply set $a$ to be $E$ in order, and set $b$ to be the unsorted list. However I do not see how you would calculate the array $a$ from the input, because $E$ is not known in advance. $\endgroup$ – SmileyCraft Mar 20 at 14:10
  • $\begingroup$ Array $a$ is postulated to be $E$ in order. Array $b$ is postulated to be arbitrary. (Or you can image that before we apply the algorithm, we have used the oracle to order $a$. We leave $b$ alone). Then let us see what it implies when we apply the linear algorithm. $\endgroup$ – Apass.Jack Mar 20 at 14:17

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.