Count unique elements in array without sorting

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"]
var count = 1;
var results = "";
for (var i = 0; i < arr.length; i++)
    if (arr[i] == arr[i+1])
      count +=1;
        results += arr[i] + " --> " + count + " times\n" ;

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.



A quick way to do this is to copy the unique elements into an Object.

var counts = {};
for (var i = 0; i < arr.length; i++) {
    counts[arr[i]] = 1 + (counts[arr[i]] || 0);

When this loop is complete the counts object will have the count of each distinct element of the array.


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


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;
}, {});

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


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.


Same as this solution, but less code.

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


Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.