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, 1, 3, 5, 3, 2], the output should be solution(a) = 3.

  There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

• For a = [2, 2], the output should be solution(a) = 2;

• For a = [2, 4, 3, 5, 1], the output should be solution(a) = -1.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.integer a

  Guaranteed constraints:

  1 ≤ a.length ≤ 105,

  1 ≤ a[i] ≤ a.length.

• [output] integer

  The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1.

풀이

int solution(int[] a) {
    // int : count
    HashMap <Integer, Integer> map1 = new HashMap<>();
    // int : idx
    HashMap <Integer, Integer> map2 = new HashMap<>();
    
    for (int i = 0; i < a.length; i ++) {
        int n = a[i];
        // 숫자별 나온 횟수 갱신
        map1.put(n, map1.getOrDefault(n, 0) + 1);
        
        // 동일 숫자가 2회 나올 때 (첫 중복) 해당 인덱스 갱신
        if (map1.get(n) == 2) map2.put(n, i);
    }
    
    if (map2.size() < 1) return -1;
    
    int min = Integer.MAX_VALUE;
    int key = 0;
    
    for (int i : map2.keySet()) {
        if (map2.get(i) < min) {
            key = i;
            min = map2.get(i);
        }
    }
    
    return key;
}