Given an positive integer N and a list of N integers A[]. Each element in the array denotes the maximum length of jump you can cover. Find out if you can make it to the last index if you start at the first index of the list.
Example 1:
Input:
N = 6
A[] = {1, 2, 0, 3, 0, 0} 
Output:
1
Explanation:
Jump 1 step from first index to
second index. Then jump 2 steps to reach 
4_{th }index, and now jump 2 steps to reach
the end.
Example 2:
Input:
N = 3
A[] =  {1, 0, 2}
Output:
0
Explanation:
You can't reach the end of the array.
Your Task:
You don't need to read input or print anything. Your task is to complete the function canReach() which takes a Integer N and a list A of size N as input and returns 1 if the end of the array is reachable, else return 0.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
0 <= A[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    def canReach(self, A, N):
        # code here 

Solutions:
class Solution:

	def canReach(self, A, N):
		if N == 1:
			return 1
		maxReach = A[0]
		for i in range(1, N):
			maxReach = max(maxReach, A[i] + i)
			if maxReach >= N - 1:
				return 1
			if i == N - 1:
				return 1
			if maxReach <= i:
				return 0
		return 1


class Solution:

	def canReach(self, A, N):
		if A[0] == 0:
			return 1
		maxindex = 0
		for i in range(N):
			if i <= maxindex:
				maxindex = max(maxindex, i + A[i])
			else:
				return 0
		return 1


class Solution:

	def canReach(self, A, N):
		jump = 1
		step = A[0]
		max_reach = A[0]
		if step == 0:
			if N == 1:
				return 1
			else:
				return 0
		for i in range(1, N):
			step -= 1
			max_reach = max(max_reach, A[i] + i)
			if step == 0:
				if i == N - 1:
					return 1
				jump += 1
				if max_reach <= i:
					return 0
				step = max_reach - i
		return 1


class Solution:

	def canReach(self, A, N):
		maxi = 0
		if N == 1:
			return 1
		for i in range(N):
			if A[i] != 0:
				maxi = max(maxi, i + A[i])
				if maxi >= N - 1:
					return 1
			elif maxi <= i:
				return 0
		return 0


class Solution:

	def canReach(self, A, N):
		if N == 1:
			return 1
		m = A[0]
		for i in range(N):
			if m == 0:
				return 0
			m = m - 1
			if A[i] > m:
				m = A[i]
		return 1


class Solution:

	def canReach(self, A, N):
		table = [0 for x in range(N)]
		table[0] = 1
		maxReached = 1
		for i in range(1, N + 1):
			if table[i - 1] == 1 or i <= maxReached:
				maxReached = max(i + A[i - 1], maxReached)
		if N <= maxReached:
			return 1
		return 0


class Solution:

	def canReach(self, A, N):
		goal = N - 1
		for i in range(N - 2, -1, -1):
			if i + A[i] >= goal:
				goal = i
		return 1 if goal <= 0 else 0


class Solution:

	def canReach(self, arr, n):
		energy = arr[0]
		for i in range(1, n):
			if energy == 0:
				return 0
			energy -= 1
			if arr[i] > energy:
				energy = arr[i]
		return 1


class Solution:

	def canReach(self, arr, n):
		goal = n - 1
		for i in range(n - 1, -1, -1):
			if i + arr[i] >= goal:
				goal = i
		return 1 if goal == 0 else 0


class Solution:

	def canReach(self, A, N):
		reach = 0
		for i in range(len(A)):
			if reach < i:
				return 0
			reach = max(reach, i + A[i])
		return 1


class Solution:

	def canReach(self, A, N):
		(pos, dis) = (0, 0)
		for i in range(N - 1):
			dis = max(dis, i + A[i])
			if pos == i:
				pos = dis
			if pos == i:
				return 0
		return 1


class Solution:

	def canReach(self, nums, N):
		if len(nums) == 1:
			return 1
		if nums[0] == 0:
			return 0
		dp = [0] * len(nums)
		dp[0] = 1
		for i in range(1, len(nums)):
			for j in range(i):
				if dp[j]:
					if nums[j] >= i - j:
						dp[i] = 1
						break
		return dp[-1]


class Solution:

	def canReach(self, A, N):
		curr = A[0]
		maxi = A[0]
		for x in range(1, N):
			if x > maxi:
				return 0
			if maxi < A[x] + x:
				maxi = A[x] + x
			if curr == x:
				curr = maxi
			if curr == N - 1:
				return 1
		return 1


class Solution:

	def canReach(self, A, N):
		c = 0
		for (i, j) in enumerate(A):
			if c < i:
				return 0
			c = max(i + j, c)
		return 1


class Solution:

	def canReach(self, A, N):
		jumps = 0
		current = 0
		maxiReachable = A[current]
		maxiAsOfNow = A[current]
		while True:
			maxiAsOfNow = max(maxiAsOfNow, current + A[current])
			if maxiAsOfNow >= N - 1:
				return 1
			if current == maxiReachable:
				jumps += 1
				if maxiAsOfNow <= maxiReachable:
					return 0
				maxiReachable = maxiAsOfNow
			current += 1
		return 0


class Solution:

	def canReach(self, A, N):
		arr = A
		final = []
		boundary = N
		final = [0] * boundary
		for i in range(boundary - 1, -1, -1):
			if i + arr[i] >= boundary - 1:
				final[i] = 1
			elif i + arr[i] < boundary - 1:
				final[i] = min(final[i + 1:i + 1 + arr[i]] if len(final[i + 1:i + 1 + arr[i]]) >= 1 else [100000]) + 1
		final[boundary - 1] = 0
		if final[0] >= 100000:
			return 0
		else:
			return 1


class Solution:

	def canReach(self, arr, N):
		idx = N - 1
		for i in range(idx, -1, -1):
			if i + A[i] >= idx:
				idx = i
		if idx == 0:
			return 1
		else:
			return 0


class Solution:

	def canReach(self, nums, N):
		count = 0
		distance = 0
		curr_pos = 0
		for i in range(len(nums) - 1):
			distance = max(i + nums[i], distance)
			if curr_pos == i:
				curr_pos = distance
		return 1 if curr_pos >= N - 1 else 0


class Solution:

	def canReach(self, A, N):
		re = 0
		i = 0
		while i < N:
			if re < i:
				return 0
			re = max(re, i + A[i])
			i += 1
		return 1


class Solution:

	def canReach(self, A, N):
		currentMaxReach = A[0]
		jump = 0
		maxReachSoFar = A[0]
		i = 0
		while i < N:
			if i <= currentMaxReach:
				maxReachSoFar = max(maxReachSoFar, i + A[i])
				if maxReachSoFar >= N - 1:
					return 1
			if currentMaxReach == i:
				jump += 1
				currentMaxReach = maxReachSoFar
			i += 1
		return 0


class Solution:

	def canReach(self, A, N):
		count = 0
		i = 0
		while i < N:
			(ind, jump) = (-1, 0)
			if A[i] + i >= N - 1:
				return 1
			for j in range(1, A[i] + 1):
				if A[i + j] + i + j > jump:
					jump = A[i + j] + i + j
					ind = i + j
			count += 1
			if ind == -1:
				return 0
			i = ind
		return 0


class Solution:

	def canReach(self, arr, n):
		reachable = [0] * n
		reachable[0] = 1
		for i in range(1, n):
			for j in range(i):
				if reachable[j] and i <= j + arr[j]:
					reachable[i] = 1
					break
		return reachable[-1]


class Solution:

	def f(self, A, ind, N, dp):
		if ind >= N - 1:
			return True
		if ind + A[ind] == ind:
			return False
		res = False
		if dp[ind] != -1:
			return dp[ind]
		for i in range(1, A[ind] + 1):
			res = self.f(A, ind + i, N, dp) or res
		dp[ind] = res
		return dp[ind]

	def canReach(self, A, N):
		target = N - 1
		while target != 0:
			temp = target - 1
			flag = True
			while temp >= 0:
				if temp + A[temp] >= target:
					target = temp
					flag = False
					break
				temp -= 1
			if flag == True:
				return 0
		return 1


class Solution:

	def get_number_of_jumps(self, a, n):
		if n == 1:
			return 1
		if n == 0 or a[0] == 0:
			return -1
		jumps = [0] * n
		for i in range(1, n):
			jumps[i] = -1
			for j in range(i):
				if j + a[j] >= i and jumps[j] != -1:
					jumps[i] = jumps[j] + 1
					break
		return jumps[-1]

	def canReach(self, A, N):
		count = self.get_number_of_jumps(A, N)
		if count == -1:
			return 0
		return 1


class Solution:

	def canReach(self, A, N):
		m = 0
		for (i, n) in enumerate(A):
			if i > m:
				return 0
			m = max(m, i + n)
		return 1


class Solution:

	def canReach(self, A, N):
		reach = A[0]
		for pos in range(1, N):
			if pos > reach:
				return 0
			elif reach >= N:
				return 1
			reach = max(reach, pos + A[pos])
		return 1


class Solution:

	def canReach(self, A, N):
		step = 0
		jump = 0
		for i in range(len(A)):
			jump = max(jump, A[i] + i)
			if i == step:
				step = jump
			if step >= len(A) - 1:
				return 1
				break
		return 0


class Solution:

	def canReach(self, A, N):
		dp = [float('inf') for i in range(N)]
		dp[0] = 1
		for i in range(N):
			for j in range(i, i + A[i] + 1):
				dp[j] = min(dp[i] + 1, dp[j])
				if j == N - 1:
					return 1
			if A[i] == 0 and dp[i + 1] == float('inf'):
				return 0
		return 0


class Solution:

	def canReach(self, A, N):
		last = N - 1
		i = last - 1
		while 0 <= i:
			if last <= i + A[i]:
				last = i
			i -= 1
		return 1 if last == 0 else 0


class Solution:

	def canReach(self, A, N):
		reachable = [True for _ in range(N)]
		return 1 if self.helper(A, N, reachable) else 0

	def helper(self, A, N, reachable, i=0):
		if N - 1 <= i:
			return True
		if not reachable[i]:
			return False
		for jump in range(A[i], 0, -1):
			if self.helper(A, N, reachable, i + jump):
				return True
		reachable[i] = False
		return False


class Solution:

	def canReach(self, A, N):
		dp = [float('inf') for _ in range(N)]
		dp[-1] = 0
		for i in reversed(range(0, N - 1)):
			distWeCanJump = A[i]
			if i + distWeCanJump >= N - 1:
				dp[i] = 1
			else:
				minEffort = float('inf')
				for j in range(i + 1, i + distWeCanJump + 1):
					minEffort = min(minEffort, dp[j])
				dp[i] = minEffort
		return 1 if dp[0] < float('inf') else 0


class Solution:

	def canReach(self, a, n):
		last = n - 1
		for i in range(last, -1, -1):
			if a[i] + i >= last:
				last = i
		if last == 0:
			return 1
		return 0


class Solution:

	def canReach(self, a, n):
		if n in [0, 1]:
			return 1
		maxReach = a[0]
		steps = a[0]
		i = 0
		jumps = 0
		while i < n - 1:
			maxReach = max(maxReach, a[i] + i)
			steps -= 1
			if steps == 0:
				if maxReach <= i:
					return 0
				steps = maxReach - i
				jumps += 1
			i += 1
		return 1


class Solution:

	def canReach(self, arr, n):
		p = n - 1
		for i in range(n - 1, -1, -1):
			if i + arr[i] >= p:
				p = i
		return int(p == 0)


class Solution:

	def canReach(self, A, N):
		reach = N - 1
		for i in range(N - 1, -1, -1):
			if i + A[i] >= reach:
				reach = i
		return 1 if reach == 0 else 0


class Solution:

	def recur(self, i, N, A, dp):
		if i >= N - 1:
			return 1
		if dp[i] != -1:
			return dp[i]
		for ind in range(1, min(A[i] + 1, N)):
			if self.recur(i + ind, N, A, dp):
				dp[i] = 1
				return 1
		return 0

	def canReach(self, A, N):
		if A[0] == 0 and N > 1:
			return 0
		tab = [0] * N
		tab[N - 1] = 1
		for i in range(N - 2, -1, -1):
			for jump in range(1, min(A[i] + 1, N)):
				if jump + i >= N - 1 or tab[i + jump] == 1:
					tab[i] = 1
					break
		return tab[0]


class Solution:

	def canReach(self, A, N):
		if len(A) == 0:
			return 1
		i = 0
		maxReach = 0
		while i <= maxReach and i < N:
			maxReach = max(maxReach, i + A[i])
			i += 1
		if maxReach >= N - 1:
			return 1
		return 0


class Solution:

	def canReach(self, a, n):
		if a == [0]:
			return 1
		if a[0] == 0:
			return 0
		if n == 1:
			return 1
		i = n - 2
		j = n - 1
		while i >= 0:
			if a[i] >= j - i:
				j = i
				if j == 0:
					return 1
				i = j - 1
			else:
				i -= 1
		return 0


class Solution:

	def canReach(self, a, n):
		goal = n - 1
		for i in range(n - 2, -1, -1):
			if i + a[i] >= goal:
				goal = i
		if goal == 0:
			return 1
		return 0


class Solution:

	def canReach(self, A, N):
		curr = A[0]
		if N == 1:
			return 1
		if curr == 0:
			return 0
		for i in range(1, N):
			curr -= 1
			if curr < A[i]:
				curr = A[i]
			elif curr == 0 and i < N - 1:
				return 0
		return 1


class Solution:

	def canReach(self, a, n):
		i = 0
		if n == 1:
			return 1
		while i < n:
			m = 0
			if a[i] == 0:
				return 0
			for j in range(1, a[i] + 1):
				if m < a[i + j] + i + j:
					m = a[i + j] + i + j
					m_ind = j
				if m >= n - 1:
					return 1
			i = i + m_ind


class Solution:

	def canReach(self, A, N):
		end = 0
		i = 0
		while i <= end and i < N:
			if end >= N - 1:
				return 1
			elif i + A[i] > end:
				end = i + A[i]
				i += 1
			elif i + A[i] == end and A[i] == 0:
				return 0
			else:
				i += 1


class Solution:

	def canReach(self, arr, n):
		max_jmp = 0
		i = 0
		while i < n and i <= max_jmp:
			max_jmp = max(max_jmp, arr[i] + i)
			i += 1
		return 1 if i == n else 0


class Solution:

	def canReach(self, A, N):
		right_max = 0
		end_max = N - 1
		for i in range(N):
			if i > right_max:
				return 0
			if A[i] + i > right_max:
				right_max = A[i] + i
			if right_max >= end_max:
				return 1
		return 0


class Solution:

	def canReach(self, A, N):
		jumps = [0] * N
		jumps[0] = 1
		for i in range(1, N):
			for j in range(0, i):
				if jumps[i]:
					break
				if A[j] + j >= i and jumps[j]:
					jumps[i] = 1
		if jumps[-1]:
			return 1
		return 0


class Solution:

	def canReach(self, a, n):
		m = a[0]
		for i in range(1, n):
			m -= 1
			if m < 0:
				return 0
			m = max(m, a[i])
		return 1


class Solution:

	def canReach(self, A, N):
		if N <= 1:
			return 1
		curr = 0
		reach = N - 1
		tempReach = 0
		maxReach = 0
		while curr < reach and A[curr] != 0:
			tempReach = curr + A[curr]
			if tempReach >= reach:
				return 1
			maxReach = tempReach + A[tempReach]
			for i in range(curr + 1, curr + A[curr]):
				if i + A[i] > maxReach:
					tempReach = i
					maxReach = i + A[i]
			curr = tempReach
		if A[curr] == 0:
			return 0
		return 1


class Solution:

	def canReach(self, A, N):
		(res, i) = (0, 0)
		while i < N and i <= res:
			res = max(res, i + A[i])
			i += 1
		if i == N:
			return 1
		else:
			return 0


class Solution:

	def canReach(self, A, N):
		goodPos = len(A) - 1
		for i in range(len(A) - 1, -1, -1):
			if i + A[i] >= goodPos:
				goodPos = i
		if goodPos == 0:
			return 1
		else:
			return 0


class Solution:

	def canReach(self, A, N):
		if A[0] == 0:
			return 1
		i = N - 1
		m = N
		while i > 0:
			if A[i] + i >= N - 1:
				m = i
			elif m != N and A[i] + i >= m:
				m = i
			i -= 1
		if A[i] >= m:
			return 1
		return 0


class Solution:

	def canReach(self, arr, n):
		if n == 1:
			return 1
		if arr[0] == 0:
			return 0
		maxReach = arr[0]
		jumps = 0
		steps = arr[0]
		for i in range(1, n - 1):
			steps -= 1
			maxReach = max(maxReach, i + arr[i])
			if steps == 0:
				jumps += 1
				steps = maxReach - i
				if steps == 0:
					return 0
		return 1


class Solution:

	def canReach(self, a, n):
		max_reach = a[0]
		steps = a[0]
		if n == 1:
			return 1
		elif a[0] == 0:
			return 0
		i = 1
		while i < n:
			if i == n - 1:
				return 1
			max_reach = max(max_reach, i + a[i])
			steps -= 1
			if steps == 0:
				if max_reach == i:
					return 0
				steps = max_reach - i
			i += 1
		return -1


class Solution:

	def canReach(self, A, N) -> bool:
		last_position = len(A) - 1
		for i in range(len(A) - 2, -1, -1):
			if i + A[i] >= last_position:
				last_position = i
		if last_position == 0:
			return 1
		else:
			return 0


class Solution:

	def canReach(self, A, N):
		i = N - 1
		while i > 0:
			for j in range(i - 1, -1, -1):
				if A[j] + j >= i:
					i = j
					break
			else:
				break
		return 1 if i == 0 else 0


class Solution:

	def canReach(self, l, n):
		i = 0
		if n == 1:
			return 1
		while i < n and l[i] != 0:
			ans = l[i]
			max = 0
			k = i
			if ans + i + 1 < n:
				k = k + 1
				for j in range(i + 1, ans + i + 1):
					if max < l[j] + j and l[j]:
						max = l[j] + j
						k = j
				i = k
			else:
				return 1
		return 0