Find k closest elements to a value in a sorted Array. Assume no duplicates.
Test cases in Scala
assert(findClosest(arr = Array.empty, target = 5, k = 3) == Set.empty) assert( findClosest(arr = (1 to 10).toArray, target = 5, k = 3) == Set(4, 5, 6) ) assert( findClosest(arr = Array(1, 2, 3, 4, 6, 8, 9, 10), target = 5, k = 3) == Set(3, 4, 6) )
Algorithm in Scala
14 lines of Scala (version 2.13), showing how concise Scala can be!
First, we need to find the closest element to the given value: Scala already provides us with a BinarySearch implementation which gives us a way to find an insertion point in an Array!
Then, based on this insertion point, we have a left range and a right range. (this is © from www.scala-algorithms.com)
Scala concepts & Hints
Def Inside Def
A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.
It is also frequently used in combination with Tail Recursion.
Drop, Take, dropRight, takeRight
Scala's `drop` and `take` methods typically remove or select `n` items from a collection.
The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').
In Scala, the 'Ordering' type is a 'type class' that contains methods to determine an ordering of specific types.
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
(1 to n)syntax produces a "Range" which is a representation of a sequence of numbers.