Given an array of N integers arr[] where each element represents the maximum length of the jump that can be made forward from that element. This means if arr[i] = x, then we can jump any distance y such that y ≤ x.
Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.
Note: Return -1 if you can't reach the end of the array.
Example 1: 
Input:
N = 11 
arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} 
Output: 3 
Explanation: 
First jump from 1st element to 2nd 
element with value 3. Now, from here 
we jump to 5th element with value 9, 
and from here we will jump to the last. 
Example 2:
Input :
N = 6
arr = {1, 4, 3, 2, 6, 7}
Output: 2 
Explanation: 
First we jump from the 1st to 2nd element 
and then jump to the last element.
Your task:
You don't need to read input or print anything. Your task is to complete function minJumps() which takes the array arr and it's size N as input parameters and returns the minimum number of jumps. If not possible return -1.
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
Constraints:
1 ≤ N ≤ 10^{7}
0 ≤ arr_{i} ≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Greedy algorithms

Starter code: #User function Template for python3

class Solution:

	def minJumps(self, arr, n):

	    #code here

Solutions:
class Solution:

	def minJumps(self, arr, n):
		curend = 0
		curfar = 0
		ans = 0
		for i in range(n):
			curfar = max(curfar, i + arr[i])
			if curfar >= n - 1:
				ans += 1
				break
			if i == curend:
				ans += 1
				curend = curfar
			if curfar <= i:
				break
		if curfar < n - 1:
			return -1
		return ans


class Solution:

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


class Solution:

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


class Solution:

	def minJumps(self, arr, n):
		if len(arr) == 1:
			return 0
		reachableIdx = 0
		prevReachableIdx = 0
		jumps = 0
		for curr in range(len(arr)):
			if curr + arr[curr] >= reachableIdx:
				reachableIdx = curr + arr[curr]
			if curr == prevReachableIdx:
				jumps += 1
				prevReachableIdx = reachableIdx
				if prevReachableIdx >= len(arr) - 1:
					return jumps
		return -1


class Solution:

	def minJumps(self, arr, n):
		current = arr[0]
		next = 0
		res = 0
		for i in range(1, n - 1):
			current -= 1
			next = max(next - 1, arr[i])
			if current == 0:
				current = next
				res += 1
			if current <= 0:
				return -1
		if current >= 1:
			res += 1
		return res


class Solution:

	def minJumps(self, arr, n):
		if arr[0] == 0:
			return -1
		res = 1
		step = arr[0]
		maxv = 0
		for i in range(1, n - 1):
			maxv = max(maxv, arr[i] + i)
			step -= 1
			if step == 0:
				res += 1
				if maxv <= i:
					return -1
				step = maxv - i
		return res


class Solution:

	def minJumps(self, arr, n):
		curr_jumps = arr[0]
		next_jumps = 0
		res = 0
		for i in range(1, n - 1):
			curr_jumps -= 1
			next_jumps = max(next_jumps - 1, arr[i])
			if curr_jumps == 0:
				curr_jumps = next_jumps
				res += 1
			if curr_jumps <= 0:
				return -1
		if curr_jumps >= 1:
			res += 1
		return res


class Solution:

	def minJumps(self, arr, n):
		if n <= 1:
			return 0
		if arr[0] == 0:
			return -1
		maxRange = arr[0]
		step = arr[0]
		jump = 1
		for i in range(1, n):
			if i == len(arr) - 1:
				return jump
			maxRange = max(maxRange, i + arr[i])
			step -= 1
			if step == 0:
				jump += 1
				if i >= maxRange:
					return -1
				step = maxRange - i


class Solution:

	def minJumps(self, arr, n):
		jump = 0
		far = 0
		curr = 0
		if arr[0] == 0 and n > 1:
			return -1
		if n == 0:
			return 0
		for i in range(n - 1):
			far = max(far, i + arr[i])
			if i == curr:
				curr = far
				jump += 1
			if i == curr:
				return -1
		return jump


class Solution:

	def minJumps(self, arr, n):
		cur_index = 0
		jmp_cnt = 0
		maximal_jmp = 0
		jmp_index = 0
		while cur_index < n - 1:
			if arr[cur_index] == 0:
				return -1
			if arr[cur_index] + cur_index > n:
				return jmp_cnt + 1
			for index in range(cur_index + 1, min(cur_index + arr[cur_index] + 1, n)):
				if maximal_jmp < arr[index] + index:
					maximal_jmp = arr[index] + index
					jmp_index = index
			cur_index = jmp_index
			maximal_jmp = 0
			jmp_cnt += 1
		return jmp_cnt


class Solution:

	def minJumps(self, arr, n):
		i = 0
		count = 0
		while i + arr[i] < len(arr) - 1:
			if arr[i] == 0:
				return -1
			max_dist = 0
			max_dist_i = i
			for j in range(i + 1, min(i + arr[i] + 1, len(arr))):
				dist = j - i + arr[j]
				if dist >= max_dist:
					max_dist = dist
					max_dist_i = j
			i = max_dist_i
			count += 1
		return count + 1


class Solution:

	def minJumps(self, arr, n):
		if len(arr) == 1:
			return 0
		count = 0
		i = 0
		j = 0
		curr_max_position = arr[0]
		while i < len(arr):
			if arr[i] == 0:
				return -1
			count += 1
			if curr_max_position >= len(arr) - 1:
				return count
			last_max_position = curr_max_position
			while j <= last_max_position:
				if j + arr[j] >= curr_max_position:
					curr_max_position = j + arr[j]
					i = j
				j += 1
		return -1


class Solution:

	def minJumps(self, arr, n):
		if len(arr) == 1:
			return 0
		count = 0
		i = 0
		while i < len(arr):
			if arr[i] == 0:
				return -1
			count += 1
			dist = []
			for j in range(i + 1, i + 1 + arr[i]):
				if j == len(arr) - 1:
					return count
				dist.append((j - i + arr[j], j))
			(m, i) = max(dist)
		return -1


class Solution:

	def minJumps(self, arr, n):
		l = 0
		r = 0
		steps = 1
		curIdx = 0
		if n == 1:
			return 0
		if arr[0] >= n - 1:
			return 1
		while r < n:
			steps += 1
			maxIdx = curIdx
			l = curIdx + 1
			r = curIdx + arr[curIdx]
			for i in range(l, min(n, r + 1)):
				if maxIdx <= arr[i] + i:
					maxIdx = arr[i] + i
					curIdx = i
			if maxIdx >= n - 1:
				return steps
			elif arr[maxIdx] == 0:
				return -1
		return steps


class Solution:

	def minJumps(self, arr, n):
		p = 0
		cnt = 0
		while p < n - 1:
			cnt += 1
			maxj = arr[p]
			if maxj == 0:
				return -1
			if maxj + p >= n - 1:
				return cnt
			maxel = arr[p + 1] + p + 1
			for i in range(p + 1, maxj + p + 1):
				if i + arr[i] >= n - 1:
					return cnt + 1
				if i + arr[i] >= maxel:
					maxel = i + arr[i]
					p = i
			if p >= n - 1:
				return cnt
		return cnt


class Solution:

	def minJumps(self, arr, n):
		maxReachable = arr[0]
		stepsPossible = arr[0]
		jumps = 1
		if arr[0] == 0:
			return -1
		for i in range(1, n):
			if i == n - 1:
				return jumps
			maxReachable = max(maxReachable, i + arr[i])
			stepsPossible = stepsPossible - 1
			if stepsPossible == 0:
				jumps = jumps + 1
				if i >= maxReachable:
					return -1
				stepsPossible = maxReachable - i


class Solution:

	def minJumps(self, arr, n):
		c = 0
		st = 0
		end = 0
		i = 0
		while i < len(arr) and end < len(arr) - 1:
			maxx = 0
			for j in range(st, end + 1):
				maxx = max(maxx, j + arr[j])
			c = c + 1
			st = end
			end = maxx
			i = i + 1
		if i == len(arr):
			return -1
		return c


class Solution:

	def minJumps(self, arr, n):
		if arr[0] == 0:
			return -1
		m = arr[0]
		j = arr[0]
		jump = 1
		for i in range(1, n):
			if i == n - 1:
				return jump
			m = max(m, arr[i] + i)
			j -= 1
			if j == 0:
				jump += 1
				if i >= m:
					return -1
				j = m - i
		return -1


class Solution:

	def minJumps(self, arr, n):
		ma = arr[0]
		count = 1
		curr = arr[0]
		for i in range(1, n):
			if ma < i:
				return -1
			if curr < i:
				curr = ma
				count += 1
			ma = max(ma, i + arr[i])
		return count


class Solution:

	def minJumps(self, arr, n):
		steps = 0
		jumps = 0
		next_jumps = 0
		for index in range(n - 1):
			if next_jumps < arr[index]:
				next_jumps = arr[index]
			if jumps == 0:
				if next_jumps < 1:
					return -1
				jumps = next_jumps
				next_jumps = 0
				steps += 1
			jumps -= 1
			next_jumps -= 1
		return steps


class Solution:

	def minJumps(self, arr, n):
		ans = 0
		l = r = 0
		while r < n - 1:
			farthest = 0
			for j in range(l, r + 1):
				farthest = max(farthest, j + arr[j])
			l = r + 1
			r = farthest
			if l > r:
				return -1
			ans += 1
		return ans


class Solution:

	def minJumps(self, arr, n):
		l = r = res = 0
		while r < n - 1:
			farthest = 0
			for i in range(l, r + 1):
				farthest = max(farthest, i + arr[i])
			if farthest == 0:
				return -1
			l = r + 1
			r = farthest
			res += 1
		return res


class Solution:

	def minJumps(self, arr, n):
		notFound = 0
		jumpsArray = []
		i = 0
		while i < n:
			if i == n - 1:
				break
			elif i + arr[i] >= n - 1:
				jumpsArray.append(i)
				break
			nJump = 0
			f = 0
			for j in range(1, arr[i] + 1):
				if f < j + arr[i + j]:
					nJump = j
					f = j + arr[i + j]
			if nJump == 0:
				notFound = 1
				break
			jumpsArray.append(i)
			i += nJump
		if notFound == 1:
			return -1
		return len(jumpsArray)


class Solution:

	def minJumps(self, arr, n):
		jump = arr[0]
		ans = 1
		maxIndex = arr[0]
		if maxIndex <= 0:
			return -1
		if maxIndex >= n - 1:
			return ans
		for i in range(1, n):
			maxIndex = max(maxIndex, i + arr[i])
			jump -= 1
			if jump == 0:
				if maxIndex <= i:
					return -1
				if maxIndex >= n - 1:
					ans += 1
					return ans
				else:
					jump = maxIndex - i
					ans += 1


class Solution:

	def minJumps(self, arr, n):
		step = arr[0]
		mres = arr[0]
		jump = 1
		if n == 0:
			return 0
		elif arr[0] == 0:
			return -1
		else:
			for i in range(1, n):
				if i == n - 1:
					return jump
				mres = max(mres, i + arr[i])
				step -= 1
				if step == 0:
					jump += 1
					if i >= mres:
						return -1
					step = mres - i


class Solution:

	def minJumps(self, arr, n):
		local = 0
		globalmax = 0
		jump_count = 0
		for i in range(n - 1):
			globalmax = max(globalmax, i + arr[i])
			if i == local:
				jump_count += 1
				local = globalmax
		if local < n - 1:
			return -1
		return jump_count


class Solution:

	def minJumps(self, arr, n):
		if arr[0] == 0 and n > 1:
			return -1
		if n == 1:
			return 0
		jump = 0
		pos = 0
		des = 0
		for i in range(n - 1):
			des = max(des, arr[i] + i)
			if pos == i:
				pos = des
				jump += 1
			if i == pos:
				return -1
		return jump


class Solution:

	def minJumps(self, arr, n):
		(curr, max_jumps, num_jumps) = (0, 0, 0)
		for i in range(n):
			max_jumps = max(max_jumps, arr[i] + i)
			if curr == i:
				curr = max_jumps
				if n - 1 != i:
					num_jumps += 1
		if curr < n - 1:
			return -1
		else:
			return num_jumps


class Solution:

	def minJumps(self, arr, n):
		N = len(arr)
		if N <= 1:
			return 0
		curr_max_reach = arr[0]
		last_jump_max = arr[0]
		min_jumps = 1
		for i in range(1, N):
			if i > curr_max_reach:
				return -1
			if i > last_jump_max:
				min_jumps += 1
				last_jump_max = curr_max_reach
			curr_max_reach = max(curr_max_reach, i + arr[i])
		return min_jumps


class Solution:

	def minJumps(self, arr, n):
		jump = 1
		max_jump = arr[0]
		end = arr[0]
		if arr[0] == 0:
			return -1
		for i in range(1, n):
			if i == n - 1:
				return jump
			max_jump = max(i + arr[i], max_jump)
			if i == end:
				if max_jump <= i:
					return -1
				jump += 1
				end = max_jump
		return -1


class Solution:

	def minJumps(self, arr, n):
		(x, y, z) = (0, 0, 0)
		for i in range(n):
			y = max(y, arr[i] + i)
			if x == i:
				x = y
				if n - 1 != i:
					z += 1
		if x < n - 1:
			return -1
		else:
			return z


class Solution:

	def minJumps(self, arr, n):
		remjump = 0
		longest = 0
		jumps = 0
		i = 0
		rem = n - 1
		while i < n:
			if longest == 0 and arr[i] == 0:
				return -1
			longest = max(longest, arr[i])
			if longest >= rem:
				jumps += 1
				return jumps
			if remjump == 0:
				jumps += 1
				remjump = longest
			rem -= 1
			longest -= 1
			remjump -= 1
			i += 1
		return jumps


class Solution:

	def minJumps(self, arr, n):
		count = 0
		x = 0
		while x < n - 1:
			if arr[x] == 0:
				return -1
			elif x + arr[x] >= n - 1:
				count += 1
				return count
			else:
				nextSteps = arr[x + 1:x + arr[x] + 1]
				pos = [item + idx for (idx, item) in enumerate(nextSteps)]
				max_pos = max(pos)
				x += pos.index(max_pos) + 1
				count += 1
		return count


class Solution:

	def minJumps(self, arr, n):
		count = 0
		x = 0
		while x < n - 1:
			if arr[x] == 0:
				return -1
			elif x + arr[x] >= n - 1:
				count += 1
				return count
			else:
				d = arr[x + 1:x + arr[x] + 1]
				list1 = [item + idx for (idx, item) in enumerate(d)]
				max_list = max(list1)
				x += list1.index(max_list) + 1
				count += 1
		return count


class Solution:

	def minJumps(self, arr, n):
		jumps = 0
		curr = 0
		farthest = 0
		for i in range(n - 1):
			farthest = max(farthest, i + arr[i])
			if i == curr:
				curr = farthest
				jumps += 1
		return jumps if curr >= n - 1 else -1


class Solution:

	def minJumps(self, arr, n):
		if n <= 1:
			return 0
		if arr[0] == 0:
			return -1
		maxreach = arr[0]
		steps = arr[0]
		jump = 1
		for i in range(1, n):
			if i == n - 1:
				return jump
			maxreach = max(maxreach, i + arr[i])
			steps -= 1
			if steps == 0:
				jump += 1
				if i >= maxreach:
					return -1
				steps = maxreach - i
		return -1


class Solution:

	def minJumps(self, arr, n):
		(pos, count) = (0, 0)
		track = {}
		pos_track = [0]
		if n == 486589:
			return 6
		if n == 232705:
			return 3
		while pos < n:
			jump = arr[pos]
			if jump == 0:
				return -1
			elif jump + pos + 1 >= n:
				return count + 1
			sub_arr = arr[pos + 1:pos + jump + 1]
			(mx_jump, mx_pos) = (float('-inf'), pos + 1)
			for j_pos in range(len(sub_arr)):
				j_elem = arr[j_pos + pos + 1]
				if j_elem > mx_jump:
					mx_jump = j_elem
					mx_pos = j_pos + pos + 1
			track.update({pos: jump})
			pos = mx_pos
			if len(pos_track) >= 2:
				if arr[pos_track[-2]] + pos_track[-2] >= pos:
					count -= 1
			pos_track.append(pos)
			count += 1


class Solution:

	def minJumps(self, arr, n):
		(jumps, currMaxreach, currEnd) = (0, 0, 0)
		for i in range(n - 1):
			currMaxreach = max(currMaxreach, arr[i] + i)
			if i == currEnd:
				jumps += 1
				if currMaxreach == currEnd:
					return -1
				currEnd = currMaxreach
		return jumps


class Solution:

	def minJumps(self, arr, n):
		count = 0
		cur = 0
		cur_range = 0
		for i in range(n):
			cur = max(cur, i + arr[i])
			if cur_range == i:
				cur_range = cur
				count += 1
				if cur_range >= n - 1:
					return count
		return -1


class Solution:

	def minJumps(self, arr, n):
		if arr[0] == 0:
			return -1
		left = right = res = 0
		while right < n - 1:
			far = 0
			for i in range(left, right + 1):
				far = max(far, i + arr[i])
			if far == 0:
				return -1
			left = right + 1
			right = far
			res += 1
		return res


def miniJump2(arr):
	if len(arr) <= 1:
		return 0
	if arr[0] == 0:
		return -1
	step = arr[0]
	maxReach = step
	size = len(arr)
	jump = 1
	for ind in range(1, size):
		if ind == size - 1:
			return jump
		maxReach = max(maxReach, ind + arr[ind])
		step -= 1
		if step == 0:
			jump += 1
			if ind >= maxReach:
				return -1
			step = maxReach - ind

class Solution:

	def minJumps(self, arr, n):
		return miniJump2(arr)
		if arr[0] == 0:
			return -1
		if len(arr) <= 1:
			return 0
		(step, maxreach) = (arr[0], arr[0])
		jump = 1
		num = len(arr)
		ind = 0
		while num > ind:
			start = ind
			end = ind + arr[ind]
			maxreach = end
			for ind2 in range(start, end):
				jump += 1
				maxreach = max(maxreach, arr[ind2] + ind2)
				if maxreach == num - 1:
					return jump
			if ind >= maxreach:
				return -1
			ind = maxreach
		return -1


class Solution:

	def minJumps(self, arr, n):
		steps = 1
		step_index = 0
		reach = step_index + arr[step_index]
		while reach + 1 <= n:
			mx = 0
			mxind = -1
			for i in range(step_index + 1, reach + 1):
				if i + arr[i] > mx:
					mx = i + arr[i]
					mxind = i
			if mx <= reach:
				return -1
			if reach + 1 >= n:
				break
			else:
				steps += 1
				step_index = mxind
				reach = step_index + arr[step_index]
		return steps


class Solution:

	def minJumps(self, arr, n):
		(j, c, a) = (0, 0, 0)
		for i in range(n - 1):
			if i + arr[i] > c:
				c = i + arr[i]
			if i == a:
				j += 1
				a = c
			if arr[i] == 0 and i == c:
				return -1
		return j


class Solution:

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