View Jump Game on LeetCode
Statistics
Time Complexity
O(n) - Each element in the input list is visited at most once, resulting in the O(n) time complexity.
Space Complexity
O(1) - Only one variable is created, resulting in the O(1) space complexity.
Runtime Beats
83.11% of other submissions
Memory Beats
90.15% of other sumbissions
Explanation
The algorithm functions by recording the maximum amount of jumps at any given moment. Tracking this allows for an easy check to see if the program has exceeded its maximum number of jumps and is no longer a valid input list.
The jumps variable is initialized to the first element, and then the program iterates through all of the list elements.
Through this iteration, the algorithm subtracts 1 for each jump and then validates the jumps; if it is valid, continue and update jumps with the largest value between the current element at i or jumps. If invalid, return False.
Solution
1
2
3
4
5
6
7
8
9
10
class Solution:
def canJump(self, nums: List[int]) -> bool:
jumps = nums[0]
for i in range(1,len(nums)):
jumps -= 1
if jumps < 0: return False
jumps = max(jumps,nums[i])
return True