55.jump-game.md

55. Jump Game

Greedy

fun canJump(nums: IntArray): Boolean {
    var maxReach = 0
    // We have to iterate all numbers, think about `[0]`.
    for (i in 0 until nums.size) {
        // If we can reach the current position
        if (maxReach >= i) {
            maxReach = max(i + nums[i], maxReach)
            if (maxReach >= nums.size - 1) return true
        }
    }
    return false
}

• Time Complexity: O(n).
• Space Complexity: O(1).

Dyanmic Programming

It's not the optimal solution, might skip it.

fun canJump(nums: IntArray): Boolean {
    val dp = BooleanArray(nums.size) 
    dp[0] = true
    for (i in 1 until nums.size) {
        var canJump = false
        for (j in i - 1 downTo 0) {
            canJump = canJump || (dp[j] && nums[j] >= i - j)
        }
        dp[i] = canJump
    }
    return dp[nums.size - 1]
}

• Time Complexity: O(n^2).
• Space Complexity: O(n).

Failed Cases

Most cases involved 0.

• [0]
• [0, 2, 3]
• [1, 0, 1, 0]