So recently, I have been asked a simple question for counting the number of duplicate elements in an array. So, for an example input array of [5, 10, 10, 5, 13, 3], number of duplicate elements would be 2.

The task was to provide a solution in a functional style with O(n) complexity for run-time. The solution provided below incurs a runtime complexity of O(n) but also the memory complexity of O(n).

def countDuplicates(numbers: Array[Int]): Int = {
        import scala.collection.immutable.Map
        numbers.foldLeft(Map.empty[Int, Int]) { (map, item) =>
            map + (item -> (map.getOrElse(item, 0) + 1))
        }.count(_._2 > 1)
    }

The solution above use foldLeft to iterate over the array to accumulate a Map of Int to Int, representing the number of times each element has occured. With each element in the iteration we increase the counter of occurence in the Map with 1.

At the end of the foldLeft operation, we count the number of elements in the map with counter value greater than 1. For this, we use count which takes in a predicate to return a boolean stating if the entry has to be counted or not.