Leetcode in Scala3 (Dotty): N-Repeated Element in Size 2N Array
A baseline imperative solution for Leetcode’s “N-Repeated Element in Size 2N Array” is as follows:
object Solution
def repeatedNTimes(a: Array[Int]): Int =
var i = 0
while (i < a.size)
var j = 1
while (j < 4 && j + i < a.size)
if (a(i) == a(i + j))
return a(i)
j += 1
i += 1
throw new IllegalArgumentException("a repeated element must exist")
It takes 560 ms to pass all tests. A functional solution as follows takes 588 ms to go through the same tests:
object Solution
def repeatedNTimes(a: Array[Int]): Int =
val v = a.toVector
val slides = v.sliding(4) ++ (2 to 3).map(v.takeRight(_))
val resOpt = slides.find(s => s.tail.contains(s.head))
resOpt match
case Some(r +: _) => r
case Some(_) => ??? // never happens
case None =>
throw IllegalArgumentException("a repeated element must exist")