Challenge

Jump Game

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.

I O n u p t u p t u : t : n u 2 m s # = r e [ a 2 c , h 4 , t 1 o , 1 i , n 1 d 7 e ] x 1 a n d t h e n f r o m t h e r e l a s t i n d e x .

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)