Jump Game II

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


Intuition

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.

Solution


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