Range Minimum Query Implementation in Scala

Question

I would like to heat some feedback on this. I'm coming from a Java background and this is my first program in Scala. I solved Range Minimum Query problem.

object Solution {
 def main(args: Array[String]){
 val readInfo = readLine.split(" ");
 val numberofElements = Integer.parseInt(readInfo(0))
 val numberOfQuery = Integer.parseInt(readInfo(1))
 val storeElemets: Array[Int] =readLine.split(" ").map(_.toInt);
 val j =0;
 for(j<-0 until numberOfQuery){
 val z = readLine.split(" ")
 val from = Integer.parseInt(z(0))
 val to = Integer.parseInt(z(1))+1
 val i=from
 val getNumber = (from until to).map{i => storeElemets(i)}
 println(getNumber.min);
 }
 }
}

I would like to know, What are the best practices and is there any better way to implement this solution ?

Answer 1

For starters, your spacing is rather inconsistent: val j =0 val i=from, typos abound: storeElements, numberOfElements numberOfQueries, and you terminate some statements with ;.

Be aware that a lambda foo => bar(foo) is similar to the declaration def anonymous(foo) = bar(foo). That is, the parameter name foo is already declared by being a parameter – your val i = from is a absolutely unnecessary. Similarly, val j = 0 is not needed because j <- ... in the for-comprehension already amounts to a declaration.

In Scala, curly braces {} and parens () are rather similar. Use curlies only when using a multi-statement lambda.

In one place, you do _.toInt, in another you Integer.parseInt(_). I'd rather use the first solution, as it is shorter.

If we clean up these minor problems (and remove some unnecessary variables), we end up with this code:

object Solution { 
 def main(args: Array[String]) {
 val readInfo = readLine.split(" ")
 val numberOfElements = readInfo(0).toInt
 val numberOfQueries = readInfo(1).toInt
 val storeElements = readLine.split(" ").map(_.toInt)
 for (i <- 0 until numberOfQueries) {
 val z = readLine.split(" ")
 val from = z(0).toInt
 val to = z(1).toInt + 1
 val getNumber = (from until to).map(i => storeElements(i))
 println(getNumber.min)
 }
 }
}

A number of things appears suspect, for example the name z which should better be range, and the +1 for the upper bound of the range. The a until b method excludes the upper bound [a, b). However, there is also a a to b function, which produces an inclusive range [a, b].

The getNumber variable has a rather weird name, and I wouldn't even assign this value to a name. The minimum is more interesting than the slice.

What (z(0).toInt to z(1).toInt).map(i => storeElements(i)) calculates is a slice of elements in the array. There is the builtin method slice for this use case (which takes the inclusive lower and exclusive upper bound as arguments).

We now have the code:

object Solution { 
 def main(args: Array[String]) {
 val problemSize = readLine.split(" ")
 val elements = problemSize(0).toInt
 val queries = problemSize(1).toInt
 val input = readLine.split(" ").map(_.toInt)
 for (i <- 0 until queries) {
 val range = readLine.split(" ")
 val minimum = input.slice(range(0).toInt, range(1).toInt + 1).min
 println(minimum)
 }
 }
}

But is this a Range Minimum Query? No, it just returns the minimal element in that slice. We are not interested in the minimal value, but rather in the position of the minimal value.

Because this is just a code review, I won't explain an algorithm for performing the RMQ, but the external links in the Wikipedia article you linked to contain a few algorithms.

Answer 2

If you really would like to get the index instead of the value I would utilise zipWithIndex, which maps the list into a Tuple2 where left is the original value and right its index.

Like so:

val result = List(0, 5, 2, 5, 4, 3, 1, 6, 3).zipWithIndex.slice(3, 8).minBy(_._1)._2
println(result)

Of course accessing tuples by _._1 and _._2 isn't very pretty or readable, but we can convert tuple into case class

case class ValueAndIndex(value: Int, index: Int)
val result = List(0, 5, 2, 5, 4, 3, 1, 6, 3).zipWithIndex.map {
 case (value, index) => ValueAndIndex(value, index)
}.slice(3, 8).minBy(_.value).index
println(result)

or even

case class ValueAndIndex(value: Int, index: Int)
val result = List(0, 5, 2, 5, 4, 3, 1, 6, 3).zipWithIndex
 .map(ValueAndIndex.apply _ tupled).slice(3, 8).minBy(_.value).index
println(result)