[CodeFights] firstDuplicate

A google problem.. The problem sounds very simple. The tricky part is the time and space constraint.

Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

• For a = [2, 3, 3, 1, 5, 2], the output should be
  firstDuplicate(a) = 3.
  There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.
• For a = [2, 4, 3, 5, 1], the output should be
  firstDuplicate(a) = -1.

The key point is that numbers are in the range from 1 to len(a). This reminds me of another leetcode problem: First missing positive.

In FirstMissingPositive, we take advantage of the same condition "numbers are in the range from 1 to len(a)" and treat the original array as a hashmap. Whenever we encounter a out-of-place number a[i], we swap it with a[a[i]-1]. If this problem only wants to find a duplicate, this method works, However, the tricky part is that we want to find the first duplicate number for which the second occurance has the minimal index. Swapping destroys the order and is hard to recover.

The way to solve this problem is to mark the "proper index" negative. By this, take above array as an example, when we first see a[1] = 3, we mark a[a[1]-1] = a[2] as negative, if later we need to visit this index again, we know we have seen this number before.

def firstDuplicate(a):
    if not a: return -1
    for i in range(len(a)):
        proper_idx = abs(a[i]) - 1
        if a[proper_idx] < 0:
            # visited before
            return abs(a[i])
        else:
            a[proper_idx] = -a[proper_idx]
    return -1