Fastest way to get ONLY unique values from 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 more than once in the students array, I do not want any of the objects with that age in my uniqueAges array. 'Abbey' and 'Colin' have the same age so they are both out.

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 is it possible to do it without a second loop? I'm not an expert on time complexity but I am trying to find if it is possible this task can be O(n).

Edit: I am not asking if uniqueAgeGetter be rewritten to read nicer or use functions like map, reduce or filter (as my understanding is they are ultimately a loop as well).

My question is can uniqueAgeGetter be refactored in a way that reduces the time complexity? Can it be done with only one loop?

Thank you.

Answer 1

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

Since ages have reasonable limits, we can use an integer array of length equal to the maximum possible age to store the age counts. In the example below, I take the maximum possible age to be a 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

• The first idea, we can do over two step:

  Step1: Sort the array

  -- There are many algorithms to do it. As I know, currently, the complexity of best algorithm now is O(Nlog(N)) with N is the number of array.

  Step2: Remove the duplicated elements

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

• The second idea

  This also has the complexity is O(Nlog(N)) but it will be O(N) for next time you want to get the unique age.

  Instead of saving the data in array, you can rebuild in a binary search tree with a little custom. This node in this tree will save all the elements with same age.

  The complexity for the first time you build the tree is O(Nlog(N))

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

Answer 3

You can use reduce

The first reduce is to summarise the array and convert it into an object using the age as a the key. Using the age as the key will make it easier to check if the age already exist. The object properties will have an array value like [2,true], where the first element is the age and the second element tells if the age has duplicates. Using Object.values will convert the object into an array.

The second reduce is to form the desired output.

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