LeetCode Entry

55. Jump Game

26.12.2022 medium 2022 kotlin

fun canJump(nums: IntArray): Boolean {

55. Jump Game medium

https://t.me/leetcode_daily_unstoppable/64

blog post

    fun canJump(nums: IntArray): Boolean {
       var minInd = nums.lastIndex
       for (i in nums.lastIndex - 1 downTo 0) {
           if (nums[i] + i >= minInd) minInd = i
       }
       return minInd == 0
    }

For any position i we can reach the end if there is a minInd such that nums[i] + i >= minInd and minInd is a known to be reaching the end. We can run from the end and update minInd - minimum index reaching the end.

Space: O(1), Time: O(N)