55. Jump Game

Description

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 <= 10⁴
• 0 <= nums[i] <= 10⁵

Submitted Code

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        max_dist = 0            # 현재 도달 가능한 최대 거리(인덱스)

        for i in range(n-1):
            max_dist = max(max_dist, (i + nums[i])) 
            if max_dist == i:
                return False

        return True

Runtime: 11 ms | Beats 92.20%
Memory: 20.29 MB | Beats 71.44%

현재까지 최대로 도달 가능한 거리만 체크하면 되기 때문에 45. Jump Game II 문제보다 더 쉽다.

Other Solutions

1st

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        
        return True if goal == 0 else False

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

뒤에서부터 거꾸로 가면서 체크하는 방법도 참고했다.

2nd

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        gas = 0
        for n in nums:
            if gas < 0:
                return False
            elif n > gas:
                gas = n
            gas -= 1
            
        return True