LeetCode 55. Jump Game

Description for this problem can be found here.

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Here is the solution in Scala.

object Solution {
  def canJump(nums: Array[Int]): Boolean = {
    nums.zipWithIndex
      .foldLeft((0, 0))((a, b) =>
        if (a._1 < b._2 + b._1 && b._2 <= a._2) (b._2 + b._1, b._2 + b._1)
        else a)
      ._1 >= (nums.size - 1)
  }
}

First we need to use zipWithIndex to create a list of tuples where first element is the actual element and second element is index of that element in the list.

//we have a list
val list = List(1,2,3,4,5)
list.zipWithIndex
// If we use zipWithIndex on the list, then we will get a list of tuples.
//List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4))

After we have the list of tuples then we use foldLeft to traverse on the list with initial value(0, 0). As we traverse we update the maximum index we can reach.

	if (a._1 < b._2 + b._1 && b._2 <= a._2) (b._2 + b._1, b._2 + b._1)
	else a

After the foldLeft operation we check whether the maximum index we can reach is greater or equal to last index.

._1 >= (nums.size - 1)

We return the boolean result of above line of code.