Python solution with detailed explanation


  • 2
    G

    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"

    • https://www.youtube.com/playlist?list=PLamzFoFxwoNgG0Q5rqfTY6ovWSTAC9mbz
    • 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
    

Log in to reply
 

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