Jump Game

Medium Subject: Greedy

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

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.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true

Optimal Solution

Python

Approach: Greedy Goal Shifting

Start from the end of the array (goal = len(nums) - 1). Iterate backwards. If the current index i plus nums[i] can reach the goal, we shift the goal to i. If after the loop the goal is 0, we can reach the end.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1
        for i in range(len(nums) - 1, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        return goal == 0