1<<-DOC
 2Note: Write a solution with O(n) time complexity and O(1) additional space complexity, 
 3since this is what you would be asked to do during a real interview.
 4
 5Given an array a that contains only numbers in the range from 1 to a.length,
 6find the first duplicate number for which the second occurrence has the minimal index.
 7In other words, if there are more than 1 duplicated numbers, 
 8return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. 
 9If there are no such elements, return -1.
10
11Example
12
13For a = [2, 3, 3, 1, 5, 2], the output should be
14firstDuplicate(a) = 3.
15
16There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, 
17so the answer is 3.
18
19For a = [2, 4, 3, 5, 1], the output should be
20firstDuplicate(a) = -1.
21
22Input/Output
23
24[time limit] 4000ms (rb)
25[input] array.integer a
26
27Guaranteed constraints:
281 ≤ a.length ≤ 105,
291 ≤ a[i] ≤ a.length.
30
31[output] integer
32
33The element in a that occurs in the array more than once and has the minimal index for its second occurrence. 
34If there are no such elements, return -1.
35DOC
36
37describe "first_duplicate" do
38  def first_duplicate(items)
39    head, tail = 0, 1
40    min = -1
41    n = items.size
42
43    until head == (n - 1) || head == min
44      puts [items[head], items[tail]].inspect
45      if items[head] == items[tail]
46        min = min < 0 ?  tail + 1 : [min, tail + 1].min
47        puts ['match', items[head], items[tail], min].inspect
48        head += 1
49        tail = head + 1
50        break if tail == head
51      else
52        tail += 1
53        break if min >= 0 && tail > min
54        if tail == n
55          head += 1
56          tail = head + 1
57        end
58      end
59    end
60    min > 0 ? items[min - 1] : min
61  end
62
63  def first_duplicate(items)
64    hash = {}
65    items.each do |item|
66      return item if hash[item]
67      hash[item] = true
68    end
69    -1
70  end
71
72  [
73    { a: [2, 3, 3, 1, 5, 2], x: 3 },
74    { a: [2, 4, 3, 5, 1], x: -1 },
75    { a: [1], x: -1 },
76    { a: [2, 2], x: 2 },
77    { a: [2, 1], x: -1 },
78    { a: [2, 1, 3], x: -1 },
79    { a: [2, 3, 3], x: 3 },
80    { a: [3, 3, 3], x: 3 },
81    { a: [8, 4, 6, 2, 6, 4, 7, 9, 5, 8], x: 6 },
82    { a: [10, 6, 8, 4, 9, 1, 7, 2, 5, 3], x: -1 },
83    { a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 9], x: 9 },
84  ].each do |x|
85    it do
86      expect(first_duplicate(x[:a])).to eql(x[:x])
87    end
88  end
89end