# Solution in Scala

• Step 1. build range map [To,Set(From)]
Step 2. from last index search in the range map ['lastIndex', [fromIndex1,fromIndex2....]]
Step 3. recursive find the least effort on find the solution

``````trait LC45Solution {

def jump(nums: Array[Int]): Int = {

val indexFromToMap = mutable.HashMap[Int,mutable.LinkedHashSet[Int]]()

val k = nums.length - 1

for (i <- 0 until nums.length) {

val from  = i
var to = i + nums(i)

if (to > k) {
to = k
}

val list = indexFromToMap.get(to).getOrElse(mutable.LinkedHashSet[Int]())
list.+(k)

}

findMinStepRecursive(indexFromToMap, k, k).getOrElse(-1)
}

fromKey:Int,
remain:Int):Option[Int] = {

if (remain == 0) {
Some(1)
}

if (remain < 0) {
None
}

var minJumpTimes = Integer.MAX_VALUE

indexFromToMap.get(fromKey).get.map( to => {

val jumpTimes = findMinStepRecursive(indexFromToMap, to, remain - fromKey).get

if (jumpTimes != None && minJumpTimes > jumpTimes + 1) {
minJumpTimes = jumpTimes
}

})

Some(minJumpTimes)

}

}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.