Frequently in software development projects there's a need for programmers to find the Kth smallest or largest element in a designated collection, in these use cases many are the approaces to fetch the Kth element such as using Min-Max heap or Quickselect. Click here for an overview of these algorithms

Implementation of a single line functional approach using Scala

This algorithm below is not the best in terms of performance but it provides a quick and effective functional way of fetching the Kth element and for small sized collections the performance overhead would be pretty much insignificant compared to other algorithms. On the other hand if dealing with large data sets and collections with a huge amount of elements the algorithms described above such as Quickselect would provide a better performance in terms of number of computations and memory usage.

This is a small application that demonstrates the functional approach:

Source code

object KthElement {
  def main(args: Array[String]): Unit = {
    val s = "aaa bbb ccc aaa bbb aaa"
    println(getKthElement(s, 2))
  }


  def getKthElement(s:String, k:Int) : String = {
    s.split(" ").toList.foldLeft(Map.empty[String, Int]) {
      (m, x) => m + ((x, m.getOrElse(x, 0) + 1))
    }.toList.sortBy(- .2).take(k).last._1
  }
}

Code explanation

1. We start by splitting the list in isolated strings and create a Map where we will store the word and its count in the string

s.split(" ").toList.foldLeft(Map.empty[String, Int])

1. Then we count each occurance of word in string and put it in the Map

{ (m, x) => m + ((x, m.getOrElse(x, 0) + 1)) }

1. Finally we convert Map to a List and sort it according to the number of counts (if MAX in descending order otherwise natural order if MIN). We take K elements from result and the last element of the list of K elements is the target Kth element we're looking for:

toList.sortBy(- .2).take(k).last._1

Source code on github