Find first unique number from array

Question

I was asked to create a function that return first UNIQUE integer from given array of integers. In a case of success the function return the unique number in a case of failure return -1. The complexity should be \$O(n \log(n))\$. How can this be improved?

function solution(A) {

    var returnNumber = -1;
    var tempArray = new Array();;

   for(i=0; i < A.length; i++){

      var newIndex = A[i];
     if( tempArray[newIndex] === undefined){
        tempArray[newIndex] = 1;
     }
     else{
        tempArray[newIndex] += 1;
     }
    }
   for(j = 0; j < A.length; j++){
     if(tempArray[A[j]] == 1){
       returnNumber = A[j];
       break;
     }
   }
    return returnNumber;
}

//var A =  [1, 4, 3, 3, 1, 2, 0, 0]; //returns 4
var A =  [22, 25, 3, 3, 1, 2, 0, 0,100,22,25,1,2]; // returns 100
solution(A)

Answer 1

Probably not the fastest. From the JS perspective, filter is just 1 loop, but indexOf and lastIndexOf are supposed to be O(n) each internally.

However, for elegance, here's code and the concept is simple: If a value appears only once in the array, then both indexOf and lastIndexOf should return the same index for a given value.

function getUniqueFromArray(arr){
  return arr.filter(function(value){
    return arr.indexOf(value) === arr.lastIndexOf(value);
  })[0] || -1;
}

var A =  [22, 25, 3, 3, 1, 2, 0, 0,100,22,25,1,2];
alert(getUniqueFromArray(A));

A more optimized solution would be to use find. It's similar to filter except for 3 things:

• It returns the match instead of an array of matches.
• Iteration stops at the first match instead of continuing to the end.
• If nothing is found, it returns undefined instead of a blank array.

The only catch is that it's only present in browsers supporting ES6.

function getUniqueFromArray(arr){
  return arr.find(function(value){
    return arr.indexOf(value) === arr.lastIndexOf(value);
  }) || -1;
}

var A =  [22, 25, 3, 3, 1, 2, 0, 0,100,22,25,1,2];
alert(getUniqueFromArray(A));

Answer 2

I like your answer. It looks a bit like a counting sort, which is very fast. I expect it's faster than a few of the other answers, although Joseph's answer is cleaner and more readable for sure. If I'm not mistaken your implementation is O(n) (which is excellent).

A couple (minor) things:

---

Using a dictionary/ hashtable would make more sense than using an array to store the frequency of each number. I'm not sure if creating an array then setting the 10,000th index (eg, if var A=[10000, 1, 1, 5]) as something takes a lot of memory (I don't use js a lot).

---

if( tempArray[newIndex] === undefined){

can just be

if(!tempArray[newIndex]){

---

Formatting. Your indentation is all over the place. This is probably due to the copy paste into the text box, but if not this is the biggest thing to make your code more readable.

---

You have 2 semi-colons:

var tempArray = new Array();;

---

Lastly, a few comments and better variable names could really help. "A" should be something more descriptive. Ps: The variable A in

function solution(A) {

doesn't have to be the same name as

var A =  [22, 25, 3, 3, 1, 2, 0, 0,100,22,25,1,2]; // returns 100
solution(A)

Though it works fine if it's the same name. I wasn't sure if this was a coincidence or because you didn't know this, but I thought I'd mention it.

---

That's about all from me... I don't code a lot in js, so any comments are welcome if I've made mistakes above (but I think most of it's pretty applicable).

Answer 3

The proposed solution by the questioner is the fastest, 2n tops if i'm correct, so O(n).

But error handling is problematic, consider the input [2,3,3,2,-1]. Is -1 the correct result or does it indicate an error?

Maybe, instead of returning only the first unique element, just return all unique elements

function uniques(xs) {

    var result, tmp, i, x;

    result = [];
    tmp = [];

    for (i in xs) {

        x = xs[i];

        tmp[x] = tmp[x] ? tmp[x]+1 : 1;

    }

    for (x in tmp) {

        if (tmp[x] === 1) {

            result[result.length] = x;

        }

    }

    return result;

}

console.log(uniques([22, 25, 3, 3, 1, 2, 0, 0,100,22,25,1,2,-1,null,NaN,[]]))

By returning an array you can still get the first unique by applying [0] to the result and indicate no unique entry with an empty array.

It also does not change your complexity: avg. n+k with k being the count for different values, but still 2n tops.

---

OLD ANSWER:

Seems to me, the more optimal concept is to remove multiple occurences once you can.

Given the worst-case scenario, that the unique element is at the ende of the array, filter and find would have to loop over all elements. Then, if indexOf and lastIndexOf are supposed to be O(n), you would be stuck with O(n^2)

(function(){

    function remove (x,xs) {

        ys = [];

        j = 0;
        for (i in xs) {

            if (x !== xs[i]) {

                ys[j] = xs[i];
                j++;

            }

        }

        return ys;

    }

    function firstUnique (xs) {

        console.log(xs.length);

        if (xs.length == 0) {

            return -1;

        }

        ys = remove(xs[0],xs);

        if (ys.length < xs.length-1) {

            return firstUnique(ys);

        }

        return xs[0];

    }

    console.log(firstUnique([22, 25, 3, 3, 1, 2, 0, 0,22,25,1,2, 100]));

}());

This way, you have only n iterations for the first application of remove. Then you reduce the size of the remaining array to at least n-2 for the next recurrence, depending on the distribution of multiple occurences.

This should sum up to O(n log n), but i'm not sure when it comes to the exact math.

This solution might be worse space-compexity-wise.