LeetCode-in-All
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
class Solution {
fun canJump(nums: IntArray): Boolean {
val sz = nums.size
// we set 1 so it won't break on the first iteration
var tmp = 1
for (i in 0 until sz) {
// we always deduct tmp for every iteration
tmp--
if (tmp < 0) {
// if from previous iteration tmp is already 0, it will be <0 here
// leading to 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 we will return false
// if either both or one of them are not 0 then we will keep doing this and check.
// 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 into 1ms 100%
// because if the test case jump value is quite large, instead of just iterate, 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 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 previous
// iteration,
// even though the next iteration index is the last one, it will return false under the
// tmp<0 condition
return true
}
}