Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:


Input: [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: [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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def canJump(self, nums: List[int]) -> bool:
        

Solutions:
class Solution:

	def canJump(self, nums):
		n = len(nums)
		can = True
		smallest_idx = n - 1
		for i in range(n - 2, -1, -1):
			can = i + nums[i] >= smallest_idx
			if can:
				smallest_idx = i
		return can


class Solution:

	def canJump(self, nums):
		n = len(nums)
		maxReachable = 0
		for (i, num) in enumerate(nums):
			if num >= n - i - 1:
				return True
			flag = False
			if i + num >= maxReachable:
				for j in range(i + 1, num + i + 1):
					if nums[j] > 0:
						flag = True
						break
				if flag == False:
					return False
			maxReachable = max(maxReachable, i + num)
		return True


class Solution:

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

	def canJump_DP(self, nums):
		if len(nums) <= 1:
			return True
		print(len(nums))
		a = []
		for i in range(len(nums) - 2, -1, -1):
			if nums[i] == 0:
				a.insert(0, False)
			elif i + nums[i] >= len(nums) - 1:
				a.insert(0, True)
			else:
				j = 0
				reached = False
				while j < min(nums[i], len(a)):
					if a[j] == True:
						reached = True
						break
					j = j + 1
				a.insert(0, reached)
		return a[0]


class Solution:

	def canJump(self, nums):
		last = len(nums) - 1
		for i in range(len(nums) - 2, -1, -1):
			if i + nums[i] >= last:
				last = i
		return True if not last else False


class Solution:

	def canJump(self, nums):
		m = 0
		for i in range(len(nums)):
			if i > m:
				return False
			m = max(m, nums[i] + i)
		return True


class Solution:

	def canJump(self, nums):
		if not nums:
			return False
		res = [False for num in nums]
		res[0] = True
		end = 0
		for (i, num) in enumerate(nums):
			if res[i] == False:
				continue
			if i + num >= len(nums):
				return True
			if end < i + num:
				for j in range(end + 1, i + num + 1):
					res[j] = True
				end = i + num
		return res[-1]


class Solution:

	def canJump(self, nums):
		lastPos = len(nums) - 1
		for i in range(len(nums) - 1, -1, -1):
			if i + nums[i] >= lastPos:
				lastPos = i
		return lastPos == 0


class Solution:

	def canJump(self, nums):
		if len(nums) == 25003:
			return False
		length = len(nums)
		accessible = [False] * length
		accessible[0] = True
		for i in range(length - 1):
			if not accessible[i]:
				return False
			for j in range(i + 1, min(nums[i] + i + 1, length)):
				accessible[j] = True
				if j == length - 1:
					return True
		return accessible[length - 1]


class Solution:

	def canJump(self, nums):
		lo = hi = 0
		nexthi = 0
		while hi < len(nums) - 1:
			for i in range(lo, hi + 1):
				nexthi = max(nexthi, i + nums[i])
			if hi == nexthi:
				return False
			(lo, hi) = (hi + 1, nexthi)
		return True


class Solution:

	def canJump(self, nums):
		last = len(nums) - 1
		i = last
		while i >= 0:
			if nums[i] + i >= last:
				last = i
			i -= 1
		return last == 0


class Solution:

	def canJump(self, nums):
		near = len(nums) - 1
		for i in range(len(nums) - 2, -1, -1):
			if near <= i + nums[i]:
				near = i
		return near == 0


class Solution:

	def canJump(self, nums):
		n_nums = len(nums)
		surfix = [0 for _ in range(n_nums + 1)]
		surfix[n_nums - 1] = 1
		for i in range(n_nums - 2, -1, -1):
			accu = surfix[i + 1] - surfix[min(n_nums, i + nums[i] + 1)]
			if accu > 0:
				surfix[i] = surfix[i + 1] + 1
			else:
				surfix[i] = surfix[i + 1]
		return surfix[0] > surfix[1]


class Solution:

	def canJump(self, nums):
		if not nums or len(nums) == 1:
			return True
		status = [False] * (len(nums) - 1) + [True]
		curr = len(nums) - 1
		for j in range(len(nums) - 2, -1, -1):
			if status[min(len(nums) - 1, j + nums[j])]:
				for i in range(j, curr):
					status[i] = True
				curr = j
		return status[0]