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.
Example 1:
Input: [2,3,1,1,4]
Output: true
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 O(N^2)
.
def function(nums):
if len(nums) == 1:
return True
output = [0] * len(nums)
last_index = len(nums) - 1
output[0] = 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)