CodeSignal Interview – firstDuplicate

https://app.codesignal.com/interview-practice/question/pMvymcahZ8dY4g75q/description

Problem

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] 4 seconds (js)
• [memory limit] 1 GB
• [input] array.integer a
• Guaranteed constraints:
  1 ≤ a.length ≤ 105,
  1 ≤ a[i] ≤ a.length.
• [output] integerThe 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.

Solution

Idea

The constraint 1 ≤ a[i] ≤ a.length is important. It gives me a hint to solve this problem.

My idea is building a mapping array. All the elements will be 0. Then I loop through the array then check the number’s appearing based on the mapping array. The number will be used as index in the mapping array.

• 0: first time –> update to 1
• 1: 2nd time –> return the number because it’s what we want.
• return -1 at the end of the function. It means that there’s no duplicate element.

Code

function solution(a) {
    // build the mapping array
    let r = new Array(a.length + 1);
    for (let i = 0; i <= a.length; i++) {
        r[i] = 0;
    }
    
    for (let i = 0; i < a.length; i++) {
        let n = a[i];
        // number appears the first time
        // mark it as 1
        if (r[n] === 0) {
            r[n] = 1;
            continue;
        };
        
        // number appears the second time
        // return the number
        if (r[n] === 1) return n;
    }
    
    return -1;
}