LeetCode-in-Scala.github.io
55. Jump Game
Medium
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 105
Solution
object Solution {
def canJump(nums: Array[Int]): Boolean = {
val sz = nums.length
// We set tmp to 1 so it won't break on the first iteration
var tmp = 1
for (i <- 0 until sz) {
// We always deduct tmp for every iteration
tmp -= 1
if (tmp < 0) {
// If from the previous iteration tmp is already 0, it will be < 0 here,
// leading to a false value
return false
}
// We get the maximum value because this value is supposed to be our iterator. If both values are 0,
// then the next iteration will return false.
// We can stop the whole iteration with this condition. Without this condition, the code runs in 2ms (79.6%).
// Adding this condition improves the performance to 1ms (100%)
// because if the test case jump value is quite large, instead of just iterating, we can
// just check using this condition.
// Example: [10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] -> we can just jump to the end without iterating the whole array.
tmp = math.max(tmp, nums(i))
if (i + tmp >= sz - 1) {
return true
}
}
// We can just return true at the end because if tmp is 0 on the previous
// iteration,
// even though the next iteration's index is the last one, it will return false under the
// tmp < 0 condition.
true
}
}