4

We have one unsorted array with distinct entries a_1, a_2, ... a_n, and we also know a shifted array a_(n-k), ...a_n, a_1, a_2, ... The goal is to find the displacement k given these two arrays. Of course there is a worst case linear algorithm O(n). But can we do better than this?

There is a hint that the answer has something to do with the k distribution. If k is distributed uniformly between 0 and n, then we have to do it within O(n). If k is distributed in otherway there might be some better way.

Improve this question
4
  • Think string search Commented Oct 30, 2016 at 8:56
  • @greybeard It's a great idea. It seems that BM algorithm might work here, if k is small, then still O(k) should be the answer. If k is large(close to n), then we can try BM algorithm. For example, we choose first n/7 entry of the original array as the matching target. We preprocess the n/7 array: build a hashtable. Since each entry is distinct, then we can start from matching the last entry, if the last entry doesn't match and doesn't exist in the hashtable, we can jump n/7 array. Therefore, for large k, we can find O(cn) method but with smaller prefactor c. Commented Oct 30, 2016 at 16:19
  • @greybeard We can choose the length to be sqrt(n), then we may get to O(sqrt(n)) Commented Oct 30, 2016 at 16:22
  • (You may get expected o(n) for "random" content, but try with almost all elements equal to get an idea about worst case.) Too complicated - just search for the first half a₁…aₚ, p=n/2 of the original array in the shifted one. (OK, there are nits like odd n=2p+1 (p: length of prefix/pattern), match at p+1: if "the rest" does not match, you have to handle a possible match at p+2 "manually".) Commented Oct 30, 2016 at 18:29

4 Answers 4

Reset to default
1

If there are no duplicates in the array (distinct entries) I would do this with a while loop and incrementing an index value k starting from 0 and comparing two items at once one from the beginning and one from the end. Such as array1[k] === array2[0] or array1[n-k] === array[0] and the index value k should be the displacement once the above comparison returns true.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Best case scenario O(k), worst still O(n). I'd do the same though
1

There is an O(sqrt(n)) solution, as the op figured out based on @greybeard's hint.

From the first list, hash the first sqrt(n) elements. For the second list, look at the elements advancing by sqrt(n) elements at each time.

However, we might ask if there is a solution that might be close to O(k) (or less!) if k is small and n is large. In fact, I claim there is an O(sqrt(k)) solution.

For that, I propose an incremental process of increasing the step size. So the algorithm looks like this:

First, grab 2 elements from the first list - hash those values (and keep position of values as lookup value, so this should be thought of as a HashMap with key being elements of the list and values being positions). Compare those elements with the first and third element from the second list. Hash the values from the second list as well. Next, look at the third element from the first list - hashing the value. In the process, see if it matches either of the elements found in the second list. Next, advance 3 elements in the second list, and compare its value - remember that values as well.

Continue like this: increase the prefix length from the first list, and at each point, increasing the step size of the second list. Whenever you grab a new element for the first list, you have to compare it with values in the second list, but that's fine because it does not significantly affect performance.

Notice that when your prefix length is p, you have already checked the first p*(p+1)/2 elements in the second list. So for a given value of k, this process will require that prefix length p is approximately sqrt(2k), which is O(sqrt(k)) as required.

Improve this answer

Comments

1

Basically, if we know that a[0] does not equal b[0], we do not need to check if a[1] equals b[1]. Extending this idea and hashing the a's, checks can go as follows:

a[0] == b[0] or b[0] in hash?   => known k's: 0
a[1] == b[2] or b[2] in hash?   => known k's: 0,1,2
a[2] == b[5] or b[5] in hash?   => known k's: 0,1,2,3,4,5
a[3] == b[9] or b[9] in hash?   => known k's: 0,1,2,3,4,5,6,7,8,9
a[4] == b[14] or b[14] in hash? => known k's: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14
...

(I think that's O(sqrt n) time and space worst case complexity.)

Improve this answer

Comments

0

maybe if you incorporate them into a hashtable. then the access and compare time for a(n-k) in the original array will be O(1).

Improve this answer

1 Comment

The time of building a hashtable will at least be O(n) right?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.