3

I'm making a function, which takes an array of values and returns an array with only unique values. For example:

var strings = ["audi", "audi", "bmw", "bmw","bmw","bmw","audi","audi", "8-()"];

Result should be:

alert( unique(strings) ); // audi, bmw, 8-()

I don't understand why my function goes into infinite loop, could anyone help please? Here is the function:

function unique(arr) {
   var result = [];
   result.push(arr[0]);

   for (var i = 1; i < arr.length; i++) {
       for (var j = 0; j < result.length; j++) {
           if  (result[j] != arr[i]) {
              result.push(arr[i]); 
           }
       }
   }

   return result;
}
Improve this question
10
  • 1
    result.push(arr[i]) makes result.length increase by 1. Commented Jul 16, 2016 at 14:07
  • your result array will never stop to grow Commented Jul 16, 2016 at 14:08
  • Have you tried stepping through your code with the debugger, or adding some console.log() statements in the loop(s)? Commented Jul 16, 2016 at 14:08
  • 1
    I don't get an infinite loop when I run the above code, but the logic is faulty. If the current arr[i] item is not equal to the first value in result then you add it to result even though it may be equal to one of the later values in result. And if it's not equal to any of the existing result values you'll add it multiple times... Commented Jul 16, 2016 at 14:11
  • 1
    Well, in spite of all the answers that pretty much just show code, be sure to analyse what you were doing so you can understand what was wrong and how it would be fixed given your original approach. Understanding these sorts of problems is very important. Commented Jul 16, 2016 at 14:23

9 Answers 9

Reset to default
7

You can make it very simpler with Set and spread operators belongs to ES6,

var unique = src => [...new Set(src)]

By the way your logic is wrong. It will not run into an infinite loop. But it will give you an undesirable result.

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

Comments

6

There is no need for nested loop. you can check the result for available values with Array.prototype.indexOf or Array.prototype.includes methods.

var strings = ["audi", "audi", "bmw", "bmw", "bmw", "bmw", "audi", "audi", "8-()"];

function unique(arr) {
  var result = [];
  result.push(arr[0]);

  for (var i = 1; i < arr.length; i++) {
    if (result.indexOf(arr[i]) === -1)
      result.push(arr[i]);


  }
  return result;
}
console.log(unique(strings))

BTW chef suggest is:

var strings = ["audi", "audi", "bmw", "bmw", "bmw", "bmw", "audi", "audi", "8-()"];
console.clear();

var result = strings.filter(function(s){ return this[s] ? false : (this[s] = true); }, Object.create(null))

console.log(result);

Improve this answer

3 Comments

there is no this in arrow functions.
This still looks like a nested loop, assuming that indexOf() is built using a loop inside, meaning the speed is O(N)^2 (the for loop times the indexOf loop)
@specimen You're right about first one which where used to increase performance of OP's implementation.
4

You can reduce the time complexity of this 

var strings = ["audi", "audi", "bmw", "bmw","bmw","bmw","audi","audi", "8-()"];

var unique = [];

strings.forEach(function(str){
  if (unique.indexOf(str) < 0) {
     unique.push(str)
  }
});

return unique;
Improve this answer

3 Comments

The .indexOf() operation is still a linear (O(n)) operation.
We can use Object over here
Right, an Object or (with ES2015) a Set instance.
4

You can make it simpler: using Array.reduce

var values = [1,2,3,4,5,5,5,5,5,6,6,6,62,2,2]

function getUniq(array) {
  return array.reduce(function(u, value) {
    if (u.indexOf(value) < 0) u.push(value)
    return u;
  }, [])
}

console.log(getUniq(values))

Improve this answer

Comments

3

You can use Set also 

var strings = ["audi", "audi", "bmw", "bmw","bmw","bmw","audi","audi", "8-()"];
var uniq = new Set(strings);

// if you need in array 
uniq = Array.from(uniq);
Improve this answer

Comments

2

You could also use a dictionary/hashtable for this. Then the total runtime should be O(N) for looping through arr once:

function unique(arr) {
    unique = {}
    for(var i=0; i<arr.length; i++) {
        unique[arr[i]]=true
    }
    return Object.keys(unique)
}

JSFiddle

Improve this answer

Comments

2

You could change the inner loop a bit and use a variable found for checking if the value is in the result array.

This variable is also needed to check if the value is to push to the result set.

Additionally you could use a break to exit the inner loop if a duplicate value is found.

function unique(arr) {
    var result = [],
        found;

    result.push(arr[0]);
    for (var i = 1; i < arr.length; i++) {
        found = false;                            // initial set to false
        for (var j = 0; j < result.length; j++) {
            if (result[j] === arr[i]) {
                found = true;                     // set to true to skip push
                break;                            // exit loop
            }
        }
        found || result.push(arr[i]);             // push only, if not found
    }
    return result;
}

var strings = ["audi", "audi", "bmw", "bmw", "bmw", "bmw", "audi", "audi", "8-()"];

console.log(unique(strings)); // audi, bmw, 8-()

A shorter ES6 proposal with Array#filter and a hash table as closure.

function unique(arr) {
    return arr.filter((temp => a => !temp[a] && (temp[a] = true))(Object.create(null)));
}

var strings = ["audi", "audi", "bmw", "bmw", "bmw", "bmw", "audi", "audi", "8-()"];

console.log(unique(strings)); // audi, bmw, 8-()

Improve this answer

4 Comments

I didn't see your answer. Sometimes it's good to check back my own answers.
Which one is better? break the loop or add found to the loop second statement? or for simplicity for( var j = 0; j < result.length && ( found = result[j] === arr[i] ) ; j++);
@mortezaT, it depends, but it's not wrong to use break. i think it is good to use all language features, where it makes sense.
That's OK and there is no issue about this doesn't work. Every where I see they say better not to use jump or break because of better readability.
0

another fastest way, it is taking 2 milli seconds check the performance

var dupEleArr = [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 20, 3, 3, 3, 32, 324, 5, 52];
var uniqueArr = dupEleArr.sort(function(a,b){
    return a-b;
}).filter(function(ele,i,arr){
   return arr.length > 3 ? arr[i] != arr[i+1] : (arr.length == 2) ? (arr[i] != arr[i+1]) : true;
});

check jsfiddle

Improve this answer

2 Comments

Using dictionary is at least 10x faster. I tried your jsfiddle with a bigger dataset: jsfiddle.net/49srtxpp/1 Your solution took 30 ms, with dict it took 3ms. See my answer. BTW: Only commented on this since you presented it as the fastest way.
hey thank you @specimen , because of you, i learn the fastest technique... see here jsfiddle.net/2en1aejr i did in 3 ways but thank you very much
0

push() Pushes a new object to the beginning of an array and pushes everything back!

Let's view the state of your arrays in the program:

arr = [A,B]    result = [A]    i = 1

j = 0 -> arr[i] = B and result[j] = A    
so we use push: result = [B,A] and j++

j = 1 -> arr[i] = B and result[j] = A
so we use push: result = [B,B,A] and j++

j = 2 -> arr[i] = B and result[j] = A
so we use push: result = [B,B,B,A] and j++

Your array keeps increasing and the check will never fail, since you append to the beginning of your array and not the end.

But even if you appended your new Item to the end, you would not get unique results, since you have to check every element in result and only if not any of the results is the same you should add your new element to the result array.

For better solutions see the other answers -> Use a Set with contains()

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.