Can this function be changed to be more efficient? memory and time

Question

I had a job interview in which I had a couple code exercises. One of which was write a function that can take a numerical array and return either the first duplicated number or -1 in the case of no duplication. I wrote the following function that answers the exercise but failed on efficiency. The problem was, I was not given a sufficient answer, so for a learning point, can someone help me write this function more efficient.

function myFunc(arr) {
    for (var i = 0; i < arr.length; i++) {
        for (var x = 0; x < arr.length; x++) {
           if ((arr[i]==arr[x]) && ( i > x)) {
            return arr[i];
           }
        }
     }
     return -1;
 }

examples of returns:
arr = {8, 4, 6, 2, 6, 4, 7, 9, 5, 8} returns 6 arr = {2, 3, 3, 1, 5, 2} returns 3

Possible duplicate of [Easiest way to find duplicate values in a JavaScript array](https://stackoverflow.com/questions/840781/easiest-way-to-find-duplicate-values-in-a-javascript-array) — Igor, Sep 28 '17 at 20:20
Your code is `O(n^2)`. Tell me. If you compare the value at index 2 with the value at index 5, why repeat yourself by comparing index 5 to index 2? Your inner loop can start at `x+1`. — , Sep 28 '17 at 20:23
the complexity, to me, is that the array can have multiple dups, IE `arr = {2, 3, 3, 1, 5, 2}` the answer would be 3 as it is the first to dup. — Shane A. Workman, Sep 28 '17 at 20:30

Nicholas Tower · Accepted Answer · 2017-09-28T23:25:55.433

3

In terms of time, you can do it in O(n). Loop through the array, and add the values to a table. As soon as you come across one that you've already added to the table, you've found your duplicate. Adding to and checking the table is O(1), so the algorithmic complexity is dominated by the loop, which is O(n)

function myFunc(arr) {
    const table = {};
    for (let i = 0; i < arr.length; i++) {
        if (table[arr[i]] === true) {
            return arr[i];
        } else {
            table[arr[i]] = true;
        }
    }
    return -1;
}

console.log(myFunc([1, 2, 1, 3, 2]));

In ES6, you could use a Set instead of an object.

edited Sep 28 '17 at 23:25

answered Sep 28 '17 at 20:43

Nicholas Tower

72,740
7
86
98

thank you, i figured it was due to the 2nd for loop just couldn't find an alternative. I suspect this will work. – Shane A. Workman Sep 28 '17 at 20:48
1

It should be mentioned that the reason this is more efficient is because object property lookup has a time complexity of of O(1), whereas array lookup has O(N). – mhodges Sep 28 '17 at 20:54

score 1 · Answer 2 · answered Sep 28 '17 at 20:23

1

You can make your loop on x start from i+1 as instead of checking if i>x in your code

for ( x = i+1; x < arr.length; x++ )

answered Sep 28 '17 at 20:23

ZiGaelle

744
1
9
21

score 0 · Answer 3 · answered Sep 28 '17 at 20:41

0

What about sort the data before search for duplicated values:

function MyFunc(arr)
{
    var sorted = arr.slice().sort();

    for (var i = 0; i < arr.length - 1; i++)
        if( sorted[i+1] == sorted[i] )
            return sorted[i];

    return -1;
}

answered Sep 28 '17 at 20:41

Lacobus

1,590
12
20

Well that is one way to do it, but not the way with this problem statement and it is not very efficient. With sort the dupe that is first may now not be first. – epascarello Sep 28 '17 at 20:45
Well, slice is O(N), and sort is O(nlog(n)), and then the for loop is O(N). Not exactly the most efficient method if your arr is very large. – mhodges Sep 28 '17 at 20:57

Can this function be changed to be more efficient? memory and time

3 Answers3