Find the element with the longest distance in a given array where each element appears twice?

Given an array of int, each int appears exactly TWICE in the array. find and return the int such that this pair of int has the max distance between each other in this array.

e.g. `[2, 1, 1, 3, 2, 3]`

``````2: d = 5-1 = 4;
1: d = 3-2 = 1;
3: d = 6-4 = 2;
return 2
``````

My ideas:

Use hashmap, key is the `a[i]`, and value is the index. Scan the `a[]`, put each number into hash. If a number is hit twice, use its index minus the old numbers index and use the result to update the element value in hash.

After that, scan hash and return the key with largest element (distance). it is O(n) in time and space.

How to do it in O(n) time and O(1) space ?

-
I think, you can clearly make it faster... just a hint - in your example, after you found that for `a[0]` distance is `5`, you don't need to check any more values at all, since the size if array is `6`. –  Petr Budnik Dec 16 '11 at 7:30
@AzzA That speeds things up for sure, however, it doesn't affect the linear asymptotic growth rate . –  Murat Dec 16 '11 at 7:40
Is this an interview question? –  Karl Knechtel Dec 16 '11 at 9:18
Any known characteristics of the numbers? Are they in a certain interval? –  Tudor Dec 16 '11 at 10:42
Are there any reasons to think it's doable `O(n)` time and `O(1)` space? –  NPE Dec 16 '11 at 13:46

You would like to have the maximal distance, so I assume the number you search a more likely to be at the start and the end. This is why I would loop over the array from start and end at the same time.

``````[2, 1, 1, 3, 2, 3]
Check if 2 == 3?
Store a map of numbers and position: [2 => 1, 3 => 6]
Check if 1 or 2 is in [2 => 1, 3 => 6] ?
``````

I know, that is not even pseudo code and not complete but just to give out the idea.

-
Storing a map would imply you're not using `O(1)` space, as the size of the map depends on the number of distinct elements in the list. The question already considered the use of a look up table. –  birryree Dec 16 '11 at 7:47
Yes, in theory if you only look at O(). But in praxis this one is faster and uses less space. He always creates a map over the whole array! –  PiTheNumber Dec 16 '11 at 8:20
The assumption is somewhat fallacious: suppose you have only "well-behaved" pairs, except for one slightly misbehaved smack in the middle: `[1, 2, 1, 3, 2, 4, 4, 5, 3, 6, 5, 6]`. Here `3` is not especially at any end. –  Matthieu M. Dec 16 '11 at 9:15
For your example the algorithm from the question will create a map over the whole array (as it does always). My version skips the middle `2, 4, 4, 5`. It is faster and it needs less space. –  PiTheNumber Dec 16 '11 at 9:29

Set iLeft index to the first element, iRight index to the second element. Increment iRight index until you find a copy of the left item or meet the end of the array. In the first case - remember distance.

Increment iLeft. Start searching from new iRight. Start value of iRight will never be decreased. Delphi code:

``````  iLeft := 0;
iRight := 1;

while iRight < Len do begin //Len = array size
while (iRight < Len) and (A[iRight] <> A[iLeft]) do
Inc(iRight); //iRight++
if iRight < Len then begin
BestNumber := A[iLeft];
MaxDistance := iRight - iLeft;
end;
Inc(iLeft); //iLeft++
iRight := iLeft + MaxDistance;
end;
``````
-
[1, 2, 2, 1, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3]: In this case after finding iLeft==0, iRight==3, you'll start looking for a pair for iLeft==1. But because iRight will never be decreased, it will never find iRight==2... so it will go to the end of array. Or maybe I don't understand the algorithm exactly... –  liori Dec 16 '11 at 13:15
@liori `iRight` is reset (`iRight = iLeft + MaxDistance`) at the end of every loop. So `iRight` does decrease. The pair of `2` will not be found in your example, but this algorithm should be able to give the right result. But as `iRight` does decrease, I doubt if it is O(n). –  fefe Dec 16 '11 at 13:38
@fefe Yes, O(n) is my mistake. Removed. –  MBo Dec 16 '11 at 13:46
@MBo , It is O(n^2). –  user1002288 Dec 16 '11 at 16:28
You can increment iRight at the same time you increment iLeft. You don't care about anything whose distance is less that what you've already found. –  phkahler Dec 19 '11 at 21:36
show 1 more comment

This algorithm is O(1) space (with some cheating), O(n) time (average), needs the source array to be non-const and destroys it at the end. Also it limits possible values in the array (three bits of each value should be reserved for the algorithm).

Half of the answer is already in the question. Use hashmap. If a number is hit twice, use index difference, update the best so far result and remove this number from the hashmap to free space . To make it O(1) space, just reuse the source array. Convert the array to hashmap in-place.

Before turning an array element to the hashmap cell, remember its value and position. After this it may be safely overwritten. Then use this value to calculate a new position in the hashmap and overwrite it. Elements are shuffled this way until an empty cell is found. To continue, select any element, that is not already reordered. When everything is reordered, every int pair is definitely hit twice, here we have an empty hashmap and an updated best result value.

One reserved bit is used while converting array elements to the hashmap cells. At the beginning it is cleared. When a value is reordered to the hashmap cell, this bit is set. If this bit is not set for overwritten element, this element is just taken to be processed next. If this bit is set for element to be overwritten, there is a conflict here, pick first unused element (with this bit not set) and overwrite it instead.

2 more reserved bits are used to chain conflicting values. They encode positions where the chain is started/ended/continued. (It may be possible to optimize this algorithm so that only 2 reserved bits are needed...)

A hashmap cell should contain these 3 reserved bits, original value index, and some information to uniquely identify this element. To make this possible, a hash function should be reversible so that part of the value may be restored given its position in the table. In simplest case, hash function is just `ceil(log(n))` least significant bits. Value in the table consists of 3 fields:

• `3` reserved bits
• `32 - 3 - (ceil(log(n)))` high-order bits from the original value
• `ceil(log(n))` bits for element's position in the original array

Time complexity is O(n) only on average; worst case complexity is O(n^2).

Other variant of this algorithm is to transform the array to hashmap sequentially: on each step `m` having `2^m` first elements of the array converted to hashmap. Some constant-sized array may be interleaved with the hashmap to improve performance when `m` is low. When `m` is high, there should be enough int pairs, which are already processed, and do not need space anymore.

-
thanks for your detailed analysis, but how to keep the hash ksys ? because you have to use hash key to search in the hash table to check whether a new element is hitted twice ? –  user1002288 Dec 29 '11 at 0:12
Half of the hash key is stored in the hash table (high-order bits). Other half is restored from position in the hash table (because hash function is reversible). For example, table size is 32, and you search for a number 33. Take the low-order bits (1), so index in the table is 1. Compare the high-order bits in this table element with the high-order bits of the number (32). If there is no match, follow the chain of conflicting values. If 32 is found somewhere in the chain, this element is hit twice. If not found, add it to the hashmap. –  Evgeny Kluev Dec 29 '11 at 11:21
In other words, part of the hash key is used to find proper hashmap entry (and not stored anywhere because it is not needed to resolve collisions). Other part of the hash key is used to resolve possible collisions (and stored in every hashmap entry). –  Evgeny Kluev Dec 29 '11 at 16:38
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://stackoverflow.com/questions/8530864/find-the-element-with-the-longest-distance-in-a-given-array-where-each-element-a", "fetch_time": 1394876154000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2014-10/segments/1394678696864/warc/CC-MAIN-20140313024456-00055-ip-10-183-142-35.ec2.internal.warc.gz", "warc_record_offset": 146642398, "warc_record_length": 19584, "token_count": 2183, "char_count": 8009, "score": 3.546875, "int_score": 4, "crawl": "CC-MAIN-2014-10", "snapshot_type": "latest", "language": "en", "language_score": 0.9164496660232544, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00013-of-00064.parquet"}