Array value with highest occurrence

Question

In an array, example [1, 2, 3, 4, 5, 2, 2, 3], what logics, methods and functions can I use to pick up the value with the highest occurrence, as in this example the 2.

Answer 1

1. "Naive" method - O(n²)

For each element of the array, scroll through the entire array counting how many times that element appears. If the number is larger than the highest found so far, upgrade, or go to the next.

var entrada = [1, 2, 3, 4, 5, 2, 2, 3];

var maior = null;
var ocorrenciasMaior = -1;

for ( var i = 0 ; i < entrada.length ; i++ ) {
  var ocorrencias = 1;
  for ( var t = i+1 ; t < entrada.length ; t++ )
    if ( entrada[i] == entrada[t] )
      ocorrencias++;
  
  if ( ocorrencias > ocorrenciasMaior ) {
    maior = entrada[i];
    ocorrenciasMaior = ocorrencias;
  }
}

document.body.innerHTML += "<p>" + maior + " (" + ocorrenciasMaior + " ocorrências)</p>";

Although this method is referred to as "naive", for small inputs it can be even the most efficient of all (because it does not have the overhead of a more complex data structure).

2. Ordering - O(n*log₂ n)

Sort the array (if it’s already sorted, even better!) and then traverse it looking for the largest sequence of contiguous elements.

var entrada = [1, 2, 3, 4, 5, 2, 2, 3];

entrada.sort();

var maior = null;
var ocorrenciasMaior = -1;

var contagem = 1;
for ( var i = 1 ; i <= entrada.length ; i++ ) {
  if ( i < entrada.length && entrada[i] == entrada[i-contagem] )
    contagem++;
  
  else if ( contagem > ocorrenciasMaior ) {
    maior = entrada[i-1];
    ocorrenciasMaior = contagem;
  }
}

document.body.innerHTML += "<p>" + maior + " (" + ocorrenciasMaior + " ocorrências)</p>";

This method is more efficient than the naive method for larger inputs, but less efficient than the methods described below. However, if for some reason your array is already sorted - or if ordering it gives you some future advantage (will you need to use it in another algorithm that also works best with ordered entries) - may be a good option.

3. Table hash - O(n)

Create an initially empty hash table. For each element of the array, make sure it is in the table. If it is not, add it with the count 1. Otherwise, increment the count. At the end, go through the table looking for the element with the highest count.

var entrada = [1, 2, 3, 4, 5, 2, 2, 3];

var ocorrencias = {};

for ( var i = 0 ; i < entrada.length ; i++ )
  ocorrencias[entrada[i]] = 1 + (ocorrencias[entrada[i]] || 0);

var maior = null;
var ocorrenciasMaior = -1;

for ( var p in ocorrencias )
    if ( ocorrencias[p] > ocorrenciasMaior ) {
        maior = p;
        ocorrenciasMaior = ocorrencias[p];
    }

document.body.innerHTML += "<p>" + maior + " (" + ocorrenciasMaior + " ocorrências)</p>";

You can replace this hash table with a tree, if comparing elements is "cheaper" than computing the hash of them (rare, but there may be situations where this is true). In that case the solution would be O(n*log₂ n).

4. Counting array - O(n)

This method is faster than the hash table, but only applies if the set of possible values is finite, not very large and known a priori.

Create an array where each index represents an element, started with zero. For each element of your input, increment the value corresponding to it in the array. At the end, go through the array looking for the element with the highest count.

var entrada = [1, 2, 3, 4, 5, 2, 2, 3];

var MAXIMO_VALOR = 10;
var ocorrencias = Array(MAXIMO_VALOR).fill(0);

for ( var i = 0 ; i < entrada.length ; i++ )
  ocorrencias[entrada[i]] = 1 + (ocorrencias[entrada[i]] || 0);

var maior = null;
var ocorrenciasMaior = -1;

for ( var i = 0 ; i < ocorrencias.length ; i++ )
    if ( ocorrencias[i] > ocorrenciasMaior ) {
        maior = i;
        ocorrenciasMaior = ocorrencias[i];
    }

document.body.innerHTML += "<p>" + maior + " (" + ocorrenciasMaior + " ocorrências)</p>";

Etc.?

These are some examples of techniques, may be Overkill for such a simple problem, but illustrate how particular situations can benefit from algorithms well-adapted to their context.

Another example that I didn’t detail would be "divide and conquer", which can be interesting (at least in theory) if you have multiple processors available to assist in the task (ex.: GPGPU). In this case you would give each processor the responsibility to count an element (naive method) and - in the end - compare the counts of all of them (although there is a certain "waste", as all would run in parallel the final result would be O(n) as the best algorithms).

Answer 2

I thought a logic that you could store the counters in an Object and using only the foreach of the Array.

As it turned out:

function maior(arr){
 if (!arr) return null;
 var b={}, g = arr[0];
 arr.forEach(function(f){
  if (!b[f]) b[f] = 0;
  b[f] += 1;
  if(b[f]>b[g]) g=f;
 })
 return g;
}

Answer 3

Best solution I could find:

var arr = [1, 2, 3, 4, 5, 2, 2, 3];

var qtd = arr.reduce(function(acc,e){acc[e] = (e in acc ? acc[e]+1 : 1); return acc}, {});

qtd['2']; //3