Speeding up this code for codefighters javascript firstDuplicate() function

Question

Per Codefighters:

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.

---

So here is what I came up with. It works but fails on the final test because it ran over 4000ms. I'm at a loss as to what else I can do. Any Ideas to improve speed?

function firstDuplicate(a) {
    var test   = [],
        lowest = undefined;

    for (var i=0; i<a.length; i++) {
        if (test.indexOf(a[i]) > -1) {
            lowest = lowest || i;
            if (i < lowest) {
                lowest = i;
            }
        }
        else {
            test.push(a[i]);
        }
    }

    return lowest ? a[lowest] : -1;
}

---

Here was my second attempt but still failing on the last test...

function firstDuplicate(a) {
    var low = undefined,
        last = -1;

    for (var i=0; i<a.length; i++) {
        last = a.lastIndexOf(a[i])
        if (last > i && (low === undefined || last < low)) {
            low = last;
        }
    }

    return low !== undefined ? a[low] : -1;
}

Answer 1

The requirements give a clue of how to solve this. The set of numbers contained in the array must match the following critera:

only numbers in the range from 1 to a.length

In other words, only positive numbers that are less than or equal to the length of the array. If the array contains ten numbers, none of them will be greater than 10.

With that insight, we have a means of keeping track of numbers that we have already seen. We can treat the numbers themselves as indexes into the array, modify the element at that index (in this case by making it negative) and if we run into the same number and the element at that index is less than zero, then we know we have seen it.

console.clear()
const test1 = [2, 3, 3, 1, 5, 2]
const test2 = [2, 4, 3, 5, 1]


function firstDuplicate(a) {
  for (let i of a) {
    let posi = Math.abs(i) - 1
    if (a[posi] < 0) return posi + 1
    a[posi] = a[posi] * -1
  }

  return -1
}

console.log(firstDuplicate(test1))
console.log(firstDuplicate(test2))
console.log(firstDuplicate([2,2]))
console.log(firstDuplicate([2,3,3]))
console.log(firstDuplicate([3,3,3]))

Original Incorrect Answer

Keep track of what numbers have already been seen and return the first one that has been seen before.

console.clear()
const test1 =   [2, 3, 3, 1, 5, 2]
const test2 = [2, 4, 3, 5, 1]

      
function firstDuplicate(a){
  const seen = {}
  for (let v of a){
    if (seen[v]) return v
    seen[v] = v
  }
  
  return -1
}

console.log(firstDuplicate(test1))
console.log(firstDuplicate(test2))

As pointed out in the comments, however, this answer takes O(n) additional space, not O(1) additional space.