Skip to content

Instantly share code, notes, and snippets.

@chenharryhua

chenharryhua/insertionSort.scala

Last active March 21, 2021 07:02
Show Gist options
  • Save chenharryhua/22b893179d7b7d4a5e28f2a15aea0d8b to your computer and use it in GitHub Desktop.
Save chenharryhua/22b893179d7b7d4a5e28f2a15aea0d8b to your computer and use it in GitHub Desktop.
Download ZIP
Raw
insertionSort.scala
// https://www.hackerrank.com/challenges/insertion-sort/problem
def insertionSort(arr: Array[Int]): Int =
arr
.foldLeft((TreeMap.empty[Int, Int], 0L)) { case ((tm, s), (v)) =>
val d = tm.rangeFrom(v + 1).values.sum
val up = tm.updatedWith(v) {
case Some(x) => Some(x + 1)
case None => Some(1)
}
(up, s + d)
}
._2
@chenharryhua
Copy link
Author

merge sort won

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment