Skip to main content

🟨 Jump Game (#55)

🔗 Problem Link​

📋 Problem Statement​

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.

💡 Examples​

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

🔑 Key Insights & Approach​

Core Observation: Track farthest reachable position. If current position > farthest, can't reach.

Why Greedy?

  • O(n) time, O(1) space
  • Track max reachable index
  • No need to try all paths

Pattern: "Greedy Max Reach" pattern.

🐍 Solution: Python​

Approach: Greedy​

Time Complexity: O(n) | Space Complexity: O(1)

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0

        for i in range(len(nums)):
            if i > max_reach:
                return False

            max_reach = max(max_reach, i + nums[i])

            if max_reach >= len(nums) - 1:
                return True

        return True

🔵 Solution: Golang​

Approach: Greedy​

Time Complexity: O(n) | Space Complexity: O(1)

func canJump(nums []int) bool {
    maxReach := 0

    for i := 0; i < len(nums); i++ {
        if i > maxReach {
            return false
        }

        maxReach = max(maxReach, i+nums[i])

        if maxReach >= len(nums)-1 {
            return true
        }
    }

    return true
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

📚 References​