Fastest way to get ONLY unique values ​​from an array?

Question

I have an array like this

students = [{name: 'Abbey', age: 25}, {name: 'Brian', age: 45}, {name: 'Colin', age: 25}, {name: 'Dan', age: 78}] 

and I want the output to be:

 uniqueAges = [45, 78] 

To be clear, if there is an age value that appears several times in the students array, I do not want any objects with this age in my uniqueAges array. Abbey and Colin are of the same age, so both of them .

I know I can do something like this and run uniqueAgeGetter(students)

  function uniqueAgeGetter(list){ var listCopy = list.slice(); var uniqueAges = list.slice(); for (var i = list.length - 1; i >= 0; i--) { for (var j = listCopy.length - 1; j >= 0; j--) { if(listCopy[j].name !== list[i].name && listCopy[j].age == list[i].age){ uniqueAges.splice(i, 1) } } } console.log(uniqueAges) return uniqueAges } 

But can this be done without a second cycle? I am not a specialist in time complexity, but I'm trying to find out if it is possible that this task can be O (n).

Edit: I am not asking if it is possible to rewrite uniqueAgeGetter to read better or use functions like map, reduce or filter (since, as I understand it, they are ultimately loops).

My question is, can uniqueAgeGetter be reorganized in such a way as to reduce time complexity? Can this be done with just one loop?

Thanks.

Answer 1

This can be done in O(n) time by counting the number of times an age has been noticed and filtering out ages with a score of more than one.

Since age has reasonable limits, we can use an integer array of length equal to the maximum possible age to store age values. In the example below, I take the maximum age possible to be comfortable 200 .

 var students = [ {name: 'Abbey', age: 25 }, {name: 'Brian', age: 45 }, {name: 'Colin', age: 25 }, {name: 'Dan', age: 78 } ]; var studentAges = students.map(val => val.age); var ageCounts = Array(200).fill(0); studentAges.forEach(age => ageCounts[age] += 1); var uniqueAges = studentAges.filter(age => ageCounts[age] == 1); console.log(uniqueAges); 

Answer 2

You can use reduce

The first reduce is to sum the array and convert it to an object using age as the key. Using age as a key will make it easier to check if age exists. The properties of the object will have an array value of type [2,true] , where the first element is age and the second element indicates whether duplicates are age. Using Object.values converts the object to an array.

The second reduce should form the desired result.

 let students = [{name: 'Abbey', age: 25 }, {name: 'Brian', age: 45 },{name: 'Colin', age: 25 }, {name: 'Dan', age: 78 }]; let uniqueAges = Object.values(students.reduce((c, v) => { if (c[v.age] === undefined) c[v.age] = [v.age, true]; else c[v.age][1] = false; return c; }, {})).reduce((c, v) => { if (v[1]) c.push(v[0]); return c; }, []); console.log(uniqueAges); 

Answer 3

• The first idea we can do in two steps:

  Step1: Sort Array

  - There are many algorithms for this. As I know, currently the complexity of the best algorithm is now O (Nlog (N)), where N is the number of arrays.

  Step 2: Remove Duplicate Items

  - The complexity of this step is O (N). Thus, in two steps, the complexity is O (N) + O (Nlog (N)). Finally, complexity O (Nlog (N))

• Second idea

  This is also O (Nlog (N)) complexity, but it will be O (N) the next time you want a unique age.

  Instead of storing data in an array, you can rebuild in a binary search tree with a little custom. This node in this tree will keep all items with the same age.

  Difficulty creating a tree for the first time - O (Nlog (N))

About an algorithm that has O (N) complexity, currently, I think there is no technique to solve it .: D

Answer 4

Here is one way to do it. I think the time complexity will be O(n^2) where n is the number of elements in the original array and m is the number of unique elements in the output array.

 const students = [ {name: 'Abbey', age: 25 }, {name: 'Brian', age: 45 }, {name: 'Colin', age: 25 }, {name: 'Dan', age: 78 } ]; const uniqueStudents = students.map(val => val.age) .sort() .reduce((current, next) => { return current.length === 0 ? [].concat(current, next) : current[current.length - 1] !== next ? [].concat(current, next) : current.slice(0, -1); }, []); console.log(uniqueStudents); 

Answer 5

You can get all ages using map() , then get the expected uniqueAges with reduce() and filter() :

 var students = [{name: 'Abbey', age: 25 }, {name: 'Brian', age: 45 }, {name: 'Colin', age: 25 }, {name: 'Dan', age: 78 }] var uniqueAges = students .map(s => s.age) .reduce(function(acc, item, index, arr){ var ageOccurrences = arr.filter(i => i == item); if(ageOccurrences.length === 1) acc.push(item) return acc; },[]); console.log(uniqueAges); 

Answer 6

🚀 The fastest way with one iteration.

 const students = [ {name: `Abbey`, age: 25}, {name: `Brian`, age: 45}, {name: `Colin`, age: 25}, {name: `Dan`, age: 78}, {name: `Dan`, age: 25} ] // no global variables function unique(key) { const occurrences = {} const list = {} return (result, next, index, {length}) => { const value = next[key] if (list[value]) { occurrences[value] = value } else { list[value] = value result.push(value) } return index === length - 1 ? result.filter(v => !occurrences[v]) : result } } const uniqueNames = students.reduce(unique(`name`), []) const uniqueAges = students.reduce(unique(`age`), []) console.log(uniqueAges)