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 ?

c++ c algorithm data-structures

Edit Report

1 Answer

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;

answered 2011-12-16T12:54:06.657

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

1 Answer

Your Answer