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

Question

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 ?

Answer 1

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.