Below is my solution for the LeetCode Jump Game
Given an array of non-negative integers, 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 my solution. It is correct but timed out the LeetCode code-checker for an array of 25000 elements.
Please can someone help me improve this code.
It seems to have a time complexity of
O(N^2) and a space complexity of O(N). I cannot work out a method faster than
def function(nums): if len(nums) == 1: return True output =  * len(nums) last_index = len(nums) - 1 output = 1 for index, number in enumerate(nums): if output[index] == 0: continue if output[index] == 1: stop_at = min(last_index, index + number) for i in range(index, stop_at + 1): output[i] = 1 if output[last_index] == 1: return True return False if __name__ == "__main__": nums = [3,2,1,0,4] output = function(nums) print(output)