class Solution:
    def can_jump(self, nums):
        last = len(nums) - 1
        for i in range(last - 1, -1, -1):
            if i + nums[i] >= last:
                last = i
        
        return last == 0

    def can_jump2(self, nums):
        max_reached = 0
        stack = [0]
        while stack:
            index = stack.pop()
            if index + nums[index] > max_reached:
                if index + nums[index] >= len(nums) - 1:
                    return True
                
                for i in range(max_reached + 1, index + nums[index] + 1):
                    stack.append(i)
                
                max_reached = index + nums[index]
        
        return False

nums = [2,3,1,0,4]
# nums = [3, 2, 1, 0, 4]
solution = Solution()
print(solution.can_jump2(nums))