revise function with for loops for efficiency

Question

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?

check this https://stackoverflow.com/questions/2228362/how-to-count-matching-values-in-array-of-javascript — Giannis Mp, Jul 09 '18 at 17:33

Pransh Tiwari · Accepted Answer · 2018-07-09T17:58:44.097

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

edited Jul 09 '18 at 17:58

answered Jul 09 '18 at 17:37

Pransh Tiwari

3,983
1
32
43

im not sure how to implement a hash table – Vladimir Mujakovic Jul 09 '18 at 17:39
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 – David Peicho Jul 09 '18 at 17:46
the function you wrote does not return the correct unique integer – Vladimir Mujakovic Jul 09 '18 at 17:48
Try it now @VladimirMujakovic – Pransh Tiwari Jul 09 '18 at 17:52
Welcome. I believe the time would have now significantly improved. – Pransh Tiwari Jul 09 '18 at 18:00

Giannis Mp · Answer 2 · 2018-07-09T18:16:22.817

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))

this was better than my function but its still not fast enough. The test tries arrays that are 10m + long — Vladimir Mujakovic, Jul 09 '18 at 18:00
I made another algorithm, try it if you want for science's sake :P — Giannis Mp, Jul 09 '18 at 18:17

revise function with for loops for efficiency

2 Answers2