3
\$\begingroup\$

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 ?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.