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.

Sheridan

Try to use Set – Prehistoric

@Prehistoric Set is great, but it is not widely supported yet – Wesle

As has been shown, O(n) complexity is quite possible. But getting an output of a well-formed array [45, 78] is not possible in a single iteration over all elements. (All the solutions here require more than one iteration over multiple elements) However, it would be possible to get the desired output in a Set while iterating over elements only once. Is that something you're interested in? – Headquarters

@Wesle The vast majority of browsers support Sets. They're an ES2015 feature, and for the most part, only the very obsolete browsers which do not get updated do not understand Sets. – Headquarters

Answer 1

• 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

Hydromechanics

Answer 2

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

Mcgean

Using an object or Map and initialising only the values that appear in the array might be faster and won't fail if the assumptions (like age being an integer between 0 and 200) are not met. – Anteroom

Valid point about not requiring assumptions, @Bergi. However, I do not believe that using a map will necessarily be faster, especially for larger inputs. The time spent hashing and rehashing and resolving hash collisions should outweigh any performance benefits (which I cannot see any of - maybe I am missing something?) – Mcgean

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

Reword

Thank you for your answer. However it is my understanding that reduce iterates over the elements in the same way as a loop, so does not make the time complexity of the function any faster. I'll edit my question. – Sheridan

Well If you are getting this from DB, you might want to query the unique values. If you are using js, You have iterates to achieve what you need (well, as far as i know.) – Reword

Please explain in your answer what your code does with that v object and the tuples in it, and why you used Object.values, and how the reduction on the c array works. That you "can use reduce" is not relevant, the same general approach can be used with any other form of looping. – Anteroom

Answer 4

Here is one way you could do it. I think the time complexity would 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);

Regimen

As far as I know, JavaScript array sort is O(n log n). – Brim

@גלעדברקן => After some additional reading, you are correct. In that case, I am really not sure what the complexity of this would actually be. :S – Regimen

I think that without the slice, the dominant complexity would be the sort so O(n log n). But each call to slice makes a copy so that has a potential of O(n^2) since current would be iterated over on each call of slice. – Brim

@גלעדברקן => Good call. I will update my response with that then. – Regimen

Answer 5

for getting unique elements

const data = [128, 128,128,121,127,127,121,121,121,121,122,125];
const uniqueData = Object.keys(data.reduce((r,c) => {r[c] = true; return r;}, {}))
console.log(uniqueData)

But doing this will sort the array and will not keep the original order of the array

Complexity O(n)

Domella

Or just do: const uniqArray = Array.from(new Set(array)); – Byblow

Answer 6

The fastest way with a single 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)

Damselfly

This actually iterates over every element twice, for O(2n) complexity (same as O(n) complexity, but yours does require two iterations - once for every reduce callback, and once at the very end when you filter). This also can't differentiate between non-strings which look the same when coerced to a string, eg 54 and '54'. – Headquarters