8

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;
}
Improve this question
2
  • The problem statement is confusing. find the first duplicate number for which the second occurrence has the minimal index. But by definition there's only one duplicate number for which the second occurrence has the minimal index. Commented Jun 24, 2017 at 16:42
  • 1
    This is a poor problem. The solution is essentially a trick. Packing multiple bits of information into one number (both the number and whether or not the value of the index at which that number occurs has been visited yet) is just an optimization trick more suited to assembly language. The solution completely breaks if any of the problem constraints are changed. The solution is hard to understand. Frankly, I consider this entire problem to be worse than a waste of time--it's actively harmful. Commented Sep 13, 2017 at 10:43

5 Answers 5

Reset to default
17

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

I think this is a good answer but I'm not sure if the space complexity is O(1) because memory requirement grows as the input grows.
@ShawnRieger Yup, there was a bug. Fixed.
@ShawnRieger Math.abs() is necessary because the code is modifying the array as it loops through it. At some point it might reach a value that is modified and try to index the array by a negative value (ie, a[-2]). That value doesn't exist, so we use the absolute value (a[2]). A regular for would work just fine; thats just a stylistic choice.
@DavidSilva I don't think this is a general technique; it's something that works because of the unique constraints of the problem. The "find duplicates in an array" is a much broader problem that is discussed much more widely.
@Bert I think I understand now. The ` Math.abs - 1` is because arrays in js are 0 indexed. And you return posi + 1 because that will give you the integer that is a duplicate. You could just as well have used Math.abs(i) instead. Maybe it would have been more obvious to me if that was the case. Anyway, nice work. Thanks!
|
6

We will take advantage of the fact that the array a contains only numbers in the range from 1 to a.length, to remember that a value has been seen by reversing the sign of whatever is in that position in the array.

function lowestDuplicate(arr) {

  for (let i = 0; i < arr.length; i++) {
    const val = Math.abs(arr[i]);
    if (arr[val - 1] < 0) return val;
    arr[val - 1] = -arr[val - 1];
  }
  return -1;
}

console.log(lowestDuplicate([1, 2, 3, 4, 3, 2, 1]));
console.log(lowestDuplicate([1, 2, 3, 4, 5]));
console.log(lowestDuplicate([5, 4, 3, 2, 2]));
console.log(lowestDuplicate([2, 2]));
console.log(lowestDuplicate([2, 3, 3]));
console.log(lowestDuplicate([3, 3, 3]));
console.log(lowestDuplicate([2, 3, 3, 1, 5, 2]));

Improve this answer

4 Comments

This doesn't meet requirements. It states "find the first duplicate number for which the second occurrence has the minimal index."
@ShawnRieger Can you give a counterexample, please?
Input: a: [2, 3, 3, 1, 5, 2] Output: 2 Expected Output: 3
@ShawnRieger But my code does in fact yield 3 for that case (see last snippet test case).
1

Python 3 version that passes the tests.

def firstDuplicate(a):
    oldies={}
    notfound=True
    for i in range(len(a)):
        try:
            if oldies[a[i]]==a[i]:
                notfound=False
                return a[i]     
        except:
            oldies[a[i]]=a[i]
    if notfound:
        return -1
Improve this answer

Comments

0

You are iterating n times in both examples.

What if the array length was 200,000,000 and the first duplicate was found at index 3? The loop is still running 200,000,000 times unnecessarily.

So the idea is to break out of the loop once you find the first duplicate. you can use break or just return.

Improve this answer

5 Comments

This fails to respond to the question, which was Any Ideas to improve speed?.
since OP is on codefights, it sounds like he wants to learn, not just be given the answer without explanation. Following my advice will bring the time complexity to less than O(n) (worst case O(n)) instead of always running at O(n). This is an idea on how to improve speed.
There is no such thing as "less than O(n)". In computational complexity theory, constants are ignored. "O(kn)" is equivalent to "O(n)", whether k is 0.0001 or 10000.
So it actually doesn't want the first duplicate, it states "find the first duplicate number for which the second occurrence has the minimal index"
Thanks for clearing that up. There is such a thing as "O(n) worst case" which is better than O(n) best case.
0

A simple solution in JS. As the question title focus, you just need to find the first duplicate of the number you already traversed. So i guess this will do:

function solution(a) {
let duplicateArray = []
for(let i=0;i<a.length;i++){
    if(duplicateArray.includes(a[i])){
        return a[i];           
    }
    duplicateArray.push(a[i])
}return -1;}

Hope this helps.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.