Jump Game

Dynamic Programming
Medium

Approach

Diagrams

Analysis

Time

O(n)

Space

O(1)
class Solution:
    def canJump(self, maxJumps):
        farthestPositionSoFar = 0

        for currentPosition, maxJump in enumerate(maxJumps):
            if currentPosition > farthestPositionSoFar:
                return False

            farthestPositionFromHere = currentPosition + maxJump
            farthestPositionSoFar = max(farthestPositionSoFar, farthestPositionFromHere)

        return True

Learn

#Greedy

Videos