How to make this greedy function faster?

I am trying to solve a problem and my code fails at one test case where the list is of length 25000. Is there any way I can make this faster. I tried using functools.lru_cache and I still can not run within the time required to complete.

This is the problem from the site

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

This is what I have tried

def can_jump(input_list):

    @lru_cache
    def helper(idx = 0):
        if idx == len(input_list) - 1:
            return True
        return any(helper(new_idx) for x in range(input_list[idx]) 
        if (new_idx := idx + x + 1) < len(input_list)) # increasing order of jumps

    return helper()

Sample test cases work

input_list = [2,3,1,1,4]
print(can_jump(input_list)) # True
input_list = [3,2,1,0,4]
print(can_jump(input_list)) # False

I have also tried going from the other direction,

return any(helper(new_idx) for x in range(input_list[idx], 0, -1) 
if (new_idx := idx + x) < len(input_list)) # decreasing order of jumps

But I still can not make this run fast enough to clear the last test case of 25000 element list, what is it that I am doing wrong here?

Answer

Ok, I think I get it. Can you try this? Please note, this is taken straight from: https://codereview.stackexchange.com/questions/223612/jump-game-leetcode

def canjump(nums):
    maximum_reachable_index = 0

    for index, max_jump in enumerate(nums):
        if index > maximum_reachable_index:
            return False

        maximum_reachable_index = max(index + max_jump, maximum_reachable_index)

    return True

Advertisement

Answer