Remove all duplicate elements in O(n) time?

Question

JavaScript

I came across a problem

console.log(getUnique([2, 3, 4, 4]));//[2, 3]
console.log(getUnique([1, 2, 3, 4, 1, 4, 4, 0]));//[2, 3, 0]

Made it like this:

const getUnique = (arr) => arr.filter((it) => arr.filter((it2) => it2 === it).length < 2)

but in the condition it was exactly O (n) algorithm to come up with and even I'm stuck

Answer 1

use extra. a data structure to store the number of occurrences of each element in the list. those. for each element in the list (complexity O(n)) you need to increment the counter in this data structure (in the case of a hash table, this is O(n) at worst and O(1) on average). and then go through the hashtable again and get all the elements from it where the counter = 1 (complexity O (n)). as a result, even the complexity for the worst case will be o(n + n + n) = O(n)
those

var inputArray = new[] { 1, 2, 3, 4, 5, 4, 3, 2, 1 };
var set = new Dictionary<int, int>();

foreach (var val in inputArray)
{
    if (!set.ContainsKey(val))
    {
        set.Add(val, 1);
    }
    else
    {
        set[val] = set[val] + 1;
    }
}

var result = new List<int>();
foreach (var val in set)
{
    if (val.Value == 1)
    {
        result.Add(val.Key);
    }
}

return result; //[5]

^ can be considered an example in pseudocode, it should read like it should without problems

Answer 2

For those who are interested, I found this solution:

const removeNonUnique = array => {
  const dict = array.reduce((acc,it) => {
    if(acc[it]){
      acc[it] = {...acc[it], count: acc[it].count + 1}
      return acc
    }
    acc[it] = {value: it, count: 1}
    return acc
  }, {})

  return Object.keys(dict).filter((it) => dict[it].count < 2)
}