# Python solution with detailed explanation

• Solution

Jump Game II https://leetcode.com/problems/jump-game-ii/

Dynamic Programming With Memoization

• Sketch the recursion tree and implement the simple solution
• Base case: i == N-1, return 0. i > N-1, return float('inf')
• Recurse through all possible jumps from index i and find the minimum
• Use a cache to memoize
• This solution gives you a run time error: maximum recursion depth exceeded while calling a Py object!
• Time Complexity: O(N^2). Also Space complexity: O(N).
``````from collections import defaultdict
class Solution(object):
def helper(self, i, nums, cache):
if i == len(nums)-1:
return 0
elif i > len(nums)-1:
return float('inf')
elif i in cache:
return cache[i]
else:
cache[i] = float('inf')
for j in range(1, nums[i]+1):
cache[i] = min(cache[i], self.helper(i+j, nums, cache)+1)
return cache[i]

def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = defaultdict(int)
return self.helper(0, nums, cache)
``````

Dynamic Programming With Cache

• What is minimum cost to reach index i? Minimum cost to reach index 0 is 0.
• For indexi, lets find all indices j less than i. Now we can take a jump from index j if and only if (i-j)<=nums[j].
• Time Complexity: O(N^2). Also Space complexity: O(N).
• This solution gives a TLE
``````class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = [float('inf')]*len(nums)
cache[0] = 0
for i in range(1, len(nums)):
for j in range(i):
if i - j <= nums[j]: # Can I take a jump from position j and reach i?
cache[i] = min(cache[i], cache[j] + 1)
return cache[-1]
``````

BFS Solution to Find the Minimum Jump

• Model it like graph search problem and apply BFS to solve it
• Even this method gives TLE since it is N^2 solution.
``````class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
q, levels = [0], -1
while len(q):
levels, new_level= levels + 1, []
for x in q:
for j in range(1, nums[x]+1):
if x + j == len(nums)-1:
return levels + 1
elif x + j < len(nums)-1:
new_level.append(x+j)
else:
break
q = new_level
return levels
``````

Greedy Approach which uses "Ladder Idea from Ideserve"

• The invariant is that at a start index, we already know the maximum jump index that can be reached.
• We therefore move from index start to current_max_index and test whether we can reach further than current_max_index. Infact, we try to be greedy - we want to pick the next start point which would make us reach the farthest from current_max_index.
• Once we update the next start point, we recognize that we took a single jump.
• Take special note of initial conditions: current_max_index, start, jumps = 0, 0, 0. This initialization helps us to tackle cases likes nums =[1]. Other when length of nums is more than 1, the first jump takes us to start index 0 and sets current_max_index to nums[0].
``````class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
current_max_index, start, jumps = 0, 0, 0
while start < len(nums):
if current_max_index >= len(nums)-1:
return jumps
for i in range(start, current_max_index+1):
if nums[i] + i > current_max_index:
start, current_max_index = i, nums[i]+i
jumps += 1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.