Jump Game

Implementation

• Optimal approach
  • Time complexity - O(n)
  • Space Complexity - O(1)

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

• Another optimal approach with the same metrics:

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 True if goal == 0 else False

• We do i + nums[i] because nums[i] represents the numbers of jumps we can make forwards based on what the question states so DO NOT MIX THAT UP
• The 0 index we want to reach above is the start, so if for any reason our goal remains unchanged it would mean that the start position was not reachable hence making the jump from start to finish impossible