1

I am creating a function that returns the unique integer from an array parameter. I have written a function that works, but it is too slow. The function passes all the logical tests but times out.

The functions accepts an argument such as this:

[9,2,1,2,1,6,1,1,6,2,8,1,8]

My Function:

function findUnique(numbers) {

        let unqNumber, matchCount,i,y;
        let len = numbers.length;

        for (i = 0; i < len; i++  ) {
                matchCount = 0;
                for (y = 0; y < len; y++ ) {
                        if (numbers[i] == numbers[y]) {
                                matchCount++;                           
                        }               
                }
                if (matchCount == 1) {
                        unqNumber = numbers[i]
                }
        }
        return unqNumber;
}

It compares each index to all other indexes and counts the occurrences. The index with only 1 occurrence is the unique number.

There is ALWAYS only ONE unique number in the array being passed in.

I know for loops are inefficient but I don't know another way to write it. Could I use filter() or map() to accomplish this faster and more efficiently?

Improve this question
3

2 Answers 2

Reset to default
1

Use hashmap. The current complexity of your code is O(n*n). Using hashmap, it will be O(n).

eg)

var temp = [9,2,1,2,1,6,1,1,6,2,8,1,8];

function findUnique(numbers) 
{
    let unqNumber,i;
    let len = numbers.length;

    var mymap = {};
    for(i = 0; i < len; i++)
    {
        if(numbers[i] in mymap)
        {
            mymap[numbers[i]]++;
        }
        else
        {
            mymap[numbers[i]] = 1;
        }
    }
    console.log(mymap);
    //{1: 5, 2: 3, 6: 2, 8: 2, 9: 1}
    for(var j in mymap) 
    {
        if(mymap[j] == 1)
        {
            unqNumber = j;
        }
    }
    return unqNumber;
}

console.log(findUnique(temp));
//9
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

im not sure how to implement a hash table
Are the integers bounded? Spatial complexity can also be something, even if there is a small chance that the array contains all integers on 64 bits
the function you wrote does not return the correct unique integer
Try it now @VladimirMujakovic
Welcome. I believe the time would have now significantly improved.
0

Here you keep track of the uniques and the numbers that appear multiple times:

input = [9,2,1,2,1,6,1,1,6,2,8,1,8];

function getUniques(array) {
  doubles = [];
  uniques = [];
  for (var i = 0; i < array.length; i++) {
    if(doubles.indexOf(array[i]) != -1) {
      continue;
    } else if(uniques.indexOf(array[i]) == -1) {
      uniques.push(array[i]);
    } else {
      doubles.push(uniques.splice(uniques.indexOf(array[i]),1)[0]);
    }
  }
  return uniques;
}
  

console.log(getUniques(input)[0]);

You can try something like this. You get each element and take it as unique or remove all the same items from the array till you find the unique one. If there are more than one unique items it returns the first.

input = [9,2,1,2,1,6,1,1,6,2,8,1,8];

function findFirstUnique(array) {
  while(array.length > 0) {
    i = array.splice(0,1)[0];
    next = array.indexOf(i);
    if(next == -1) {
      return i;
    }
    while(next != -1) {
      array.splice(next,1);
      next = array.indexOf(i);
    }
  }
}

console.log(findFirstUnique(input))

Improve this answer

2 Comments

this was better than my function but its still not fast enough. The test tries arrays that are 10m + long
I made another algorithm, try it if you want for science's sake :P

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.