Jump Game in Python

Suppose we have an array of non-negative integers; we are initially positioned at the first index of the array. Each element in the given array represents out maximum jump length at that position. We have to determine if we are able to reach the last index or not. So if the array is like [2,3,1,1,4], then the output will be true. This is like jump one step from position 0 to 1, then three step from position 1 to the end.

Let us see the steps −

• n := length of array A – 1
• for i := n – 1, down to -1
  • if A[i] + i > n, then n := i
• return true when n = 0, otherwise false

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution(object):    def canJump(self, nums):       n = len(nums)-1       for i in range(n-1,-1,-1):          if nums[i] + i>=n:             n = i       return n ==0 ob1 = Solution() print(ob1.canJump([2,3,1,1,4]))

Input

[2,3,1,1,4]

Output

True