Count unique elements in array without sorting

Question

In JavaScript the following will find the number of elements in the array. Assuming there to be a minimum of one element in the array

arr = ["jam", "beef", "cream", "jam"]
arr.sort();
var count = 1;
var results = "";
for (var i = 0; i < arr.length; i++)
{
    if (arr[i] == arr[i+1])
    {
      count +=1;
    }
    else
    {
        results += arr[i] + " --> " + count + " times\n" ;
        count=1;
    }
}

Is it possible to do this without using sort() or without mutating the array in any way? I would imagine that the array would have to be re-created and then sort could be done on the newly created array, but I want to know what's the best way without sorting. And yes, I'm an artist, not a programmer, your honour.

Answer 1

The fast way to do this is with a new Set() object.

Sets are awesome and we should use them more often. They are fast, and supported by Chrome, Firefox, Microsoft Edge, and node.js.
— What is faster Set or Object? by Andrei Kashcha

The items in a Set will always be unique, as it only keeps one copy of each value you put in. Here's a function that uses this property:

function countUnique(iterable) {
  return new Set(iterable).size;
}

console.log(countUnique('banana')); //=> 3
console.log(countUnique([5,6,5,6])); //=> 2
console.log(countUnique([window, document, window])); //=> 2

This can be used to count the items in any iterable (including an Array, String, TypedArray, and arguments object).

Answer 2

Why not something like:

var arr = ["jam", "beef", "cream", "jam"]
var uniqs = arr.reduce((acc, val) => {
  acc[val] = acc[val] === undefined ? 1 : acc[val] += 1;
  return acc;
}, {});
console.log(uniqs)

Pure Javascript, runs in O(n). Doesn't consume much space either unless your number of unique values equals number of elements (all the elements are unique).

Answer 3

Same as this solution, but less code.

let counts = {};
arr.forEach(el => counts[el] = 1  + (counts[el] || 0))

Answer 4

This expression gives you all the unique elements in the array without mutating it:

arr.filter(function(v,i) { return i==arr.lastIndexOf(v); })

You can chain it with this expression to build your string of results without sorting:

.forEach(function(v) {
     results+=v+" --> " + arr.filter(function(w){return w==v;}).length + " times\n";
});

In the first case the filter takes only includes the last of each specific element; in the second case the filter includes all the elements of that type, and .length gives the count.

Answer 5

This answer is for Beginners. Try this method you can solve this problem easily. You can find a full lesson for reduce, filter, map functions from This link.

const user = [1, 2, 2, 4, 8, 3, 3, 6, 5, 4, 8, 8];

const output = user.reduce(function (acc, curr) {
    if (acc[curr]) {
        acc[curr] = ++acc[curr];
    } else {
        acc[curr] = 1;
    }
    return acc;
}, {});

console.log(output);

Answer 6

function reomveDuplicates(array){
        var newarray = array.filter( (value, key)=>{
            return array.indexOf(value) == key
        });
        console.log("newarray", newarray);
    }
reomveDuplicates([1,2,5,2,1,8]);  

Using hash Map with the time complexity O(n)

function reomveDuplicates(array){

    var obj ={};
    let res=[];

    for( arg of array){
        obj[arg] = true;
    }

    console.log(Object.keys(obj));


    for(key in obj){
        res.push(Number(key));  // Only if you want in Number 
    }

    console.log(res);
}
reomveDuplicates([1,2,5,2,1,8]);  

Answer 7

In a modern, extensible and easy-to-read approach, here's one using iter-ops library:

import {pipe, distinct, count} from 'iter-ops';

const arr = ['jam', 'beef', 'cream', 'jam'];

const count = pipe(arr, distinct(), count()).first;

console.log(count); //=> 3

Answer 8

function check(arr) {
    var count = 0;

 for (var ele of arr) {
   
    if (typeof arr[ele] !== typeof (arr[ele+1])) {
      count++;
    } else {
      ("I don't know");
    }
  }
  return count;
}