Jump Game II

Problem Id: 45 Difficulty: Hard Tag: Array Tag: Greedy


Each time, we jump to the point which could get the furthest next value. This could be done by using an additional variable to mark the next furthest jump.


class Solution:
    def jump(self, nums: List[int]) -> int:
        steps = 0
        reachable = 0
        furthest = 0
        for i, num in enumerate(nums):
            if i > reachable:
                steps += 1
                reachable = furthest

            furthest = max(i + num, furthest)

        return steps