Jump game

jump_game.py

"""
https://scammingthecodinginterview.com
Week 3: Greedy
Problem: 1
"""


from typing import List


class Solution(object):

    def solve(self, a: List[int]) -> bool:

        n = len(a)
        index = 0
        reach = 0

        while index < n and index <= reach:
            reach = max(reach, index + a[index])

            if reach >= n-1:
                break

            index += 1

        return reach >= n-1


if __name__ == "__main__":

    a = [3, 2, 1, 0, 4]
    ans = Solution().solve(a)
    print(ans)