Challenge
Given an array of positive intege, each element represents the max length, you need to find the min number of jump in order to reach the end of the array.
Input: nums = [2,4,1,1,17]
Output: 2 # reach to index 1 and then from there last index.
Solution - Recursion (TLE)
class Solution:
def helper(self, nums, current_index, steps, l, previous):
# ending recursion early if already above
if len(previous) >= self.m:
return
if current_index >=l-1:
self.m = min(self.m, len(previous))
return
for i in range(1, steps + 1):
if current_index + i < l:
self.helper(nums, current_index + i, nums[current_index + i],l, previous + [1])
def min_jump(self, nums: List[int]):
if not nums:
return 0
self.m = float('inf')
previous = []
self.helper(nums, 0, nums[0], len(nums), previous)
return self.m
Solution 2 - Memoization
class Solution:
def helper(self, nums, current_index):
if current_index >= len(nums)-1:
return 0
if current_index in self.memo:
return self.memo[current_index]
steps = nums[current_index]
for i in range(1, steps+1):
self.m = min(self.m, 1 + self.helper(nums, current_index + i))
self.memo[current_index] = self.m
return self.m
def min_jump(self, nums: List[int]):
if not nums:
return 0
self.m = float('inf')
self.memo = {}
return self.helper(nums, 0)