How to find the most common elements of an array?

Question

How to write a function that takes an array of integers, and returns an array of integers. The return value should contain those integers which are most common in the input array.

List(5, 4, 3, 2, 4, 5, 1, 6, 1, 2, 5, 4)  => List(5, 4)
List(1, 2, 3, 4, 5, 1, 6, 7)              => List(1)
List(1, 2, 3, 4, 5, 6, 7)                 => List(1, 2, 3, 4, 5, 6, 7)

I have already tried the following approach:

def mostFreq(info: List[List[String]]): (String, Int) = 
  info.flatten.groupBy(identity).mapValues(_.size).maxBy(_._2)

but it does not handle the ties.

Answer 1

You can capture the max frequency similar to what you've come up with via groupBy/mapValues/maxBy, then apply collect to the frequency Map to obtain the list of elements with the max frequency, as shown below:

val list = List(5, 4, 3, 2, 4, 5, 1, 6, 1, 2, 5, 4)

val freqMap = list.groupBy(identity).mapValues(_.size)

val maxFreq = freqMap.maxBy(_._2)._2

freqMap.collect{ case (elem, freq) if freq == maxFreq => elem }
// res1: scala.collection.immutable.Iterable[Int] = List(5, 4)

Answer 2

An alternative to Leo's answer based on Scala 2.13 which allows us to additionally handle empty lists:

val list = List(5, 4, 3, 2, 4, 5, 1, 6, 1, 2, 5, 4)
val freqMap = list.groupMapReduce(identity)(_ => 1)(_+_)
// HashMap(5 -> 3, 1 -> 2, 6 -> 1, 2 -> 2, 3 -> 1, 4 -> 3)
val maxFreq = freqMap.maxByOption(_._2).map(_._2)
// Option[Int] = Some(3)
maxFreq.map(max => freqMap.collect { case (x, f) if f == max => x }).getOrElse(Nil)
// List(5, 4)

This:

• Creates a frequency map with Scala 2.13's new groupMapReduce:

  • groups items (group part of groupMapReduce)

  • maps each grouped value occurrence to 1 (map part of groupMapReduce)

  • reduces values within a group of values (_ + _) by summing them (reduce part of groupMapReduce).

• Retrieves an optional maximum frequency using Scala 2.13's new maxByOption in order to avoid an exception on empty input lists.

• And finally maps the optional max frequency in order to collect only items with the max frequency and otherwise return an empty list.