Algorithm goal

The median value of a sorted list is the value right in the middle. In case the list is even, the average of the two middle elements is taken. For example, the median of [1,2,9] is 2, and the median of [1,2,3,9] is 2.5 (= (2 + 3) / 2).

Efficiently compute the median of two sorted arrays.

Test cases in Scala

Algorithm in Scala

40 lines of Scala (compatible versions 2.13 & 3.0).

Explanation

The brute-force solution of adding two arrays to each other requires a sort, which is O(nlogn). The efficient solution is O(n).

In order to approach this problem, first we must consider the length of both arrays, L(A) and L(B): The median of the two lists is at the half-way of L(A)+L(B) combined (≈(L(A)+L(B))/2). So the length of each side must be the same (assuming even case, and one-off otherwise). (this is © from www.scala-algorithms.com)

Assume the largest value of A is smaller than the largest value of B (this is the reason behind doing 'notRightEnd', and 'defRightEnd'). Then we are certain that the last element of the final output is coming from B.

Scala concepts & Hints

1. Class Inside Def

   Like Def Inside Def, classes can also be defined in defs.

   This is particularly useful when defining temporary data types, in particular groupings.

   type Language = String
   
   type Color = String
   
   type Translation = String
   
   def generateColors: Map[(Language, Color), Translation] = {
     final case class ColorMapping(red: String, green: String, blue: String) {
       def toMap: Map[String, String] =
         Map("red" -> red, "green" -> green, "blue" -> blue)
     }
     val translations = Map(
       "Spanish" -> ColorMapping("rojo", "verde", "azul"),
       "French" -> ColorMapping("rouge", "vert", "bleu"),
       "Chinese" -> ColorMapping("红", "绿", "蓝")
     )
   
     for {
       (language, mapping) <- translations
       (color, translation) <- mapping.toMap
     } yield (language, color) -> translation
   }
   
   assert(generateColors.contains("Spanish" -> "red"))
   
   assert(!generateColors.contains("German" -> "red"))
   

   ▶ Run code in the IDE

2. Def Inside Def

   A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.

   def exampleDef(input: String): String = {
     def surroundInputWith(char: Char): String = s"$char$input$char"
     surroundInputWith('-')
   }
   
   assert(exampleDef("test") == "-test-")
   

   ▶ Run code in the IDE

   It is also frequently used in combination with Tail Recursion.

3. For-comprehension

   The for-comprehension is highly important syntatic enhancement in functional programming languages.

   val Multiplier = 10
   
   val result: List[Int] = for {
     num <- List(1, 2, 3)
     anotherNum <-
       List(num * Multiplier - 1, num * Multiplier, num * Multiplier + 1)
   } yield anotherNum + 1
   
   assert(result == List(10, 11, 12, 20, 21, 22, 30, 31, 32))
   

   ▶ Run code in the IDE

4. Option Type

   The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!

   assert(Option(1).flatMap(x => Option(x + 2)) == Option(3))
   
   assert(Option(1).flatMap(x => None) == None)
   

   ▶ Run code in the IDE

5. Range

   The (1 to n) syntax produces a "Range" which is a representation of a sequence of numbers.

   assert((1 to 5).toString == "Range 1 to 5")
   
   assert((1 to 5).reverse.toString() == "Range 5 to 1 by -1")
   
   assert((1 to 5).toList == List(1, 2, 3, 4, 5))
   

   ▶ Run code in the IDE