Beyond awesome | 越而胜己

Link to problem: https://leetcode.com/problems/jump-game-ii/

We can build a graph (a DAG, to be exact), with the indices in nums as the vertices, and add an edge (i,j) if and only if i < j <= i+nums[i]. We need to find the shortest path from vertex 0 to vertex len(nums)-1.

The easiest way to approach this problem is using breadth first search (BFS). Because BFS does level-order traversal, in an unweighted graph, the vertices in level l have distance l to the origin. Generally BFS requires using a queue, but for this problem specifically, we can find the (upper) boundary of a level easily, which is the maximum of i+nums[i] for every vertex i in the previous level. Note that level 0 has only 1 vertex, 0. If the boundary of level l reaches or goes past the last element in nums (len(nums)-1), then the last element is in level l, i.e. the distance from it to the origin 0 is l.

Because we only traverse the array once, the time complexity of this algorithm is $\O(n)$. Obviously we only use constant extra space.

我们可以把 nums 中的每个下标作为定点构建一张(有向无环)图。对图中的每一个结点 i 和满足 i < j <= i+nums[i] 的所有 j,构造一条边 (i,j)。在这个图上寻找从结点 0 到结点 len(nums)-1 的最短路径即可。

最方便的解决方案是用广度优先搜索(BFS)。由于 BFS 逐层遍历的性质,在无权图中在第 l 层的结点离原点的距离即是 l。一般的 BFS 算法需要使用一个队列,但是由于这道题目的特殊性,我们可以知道每一层的边界,即是对上一层的所有结点 ii+nums[i] 的最大值。如果有一层 l 的边界达到或者超过了最后一个元素,那么最后一个元素 len(nums)-i 就在第 l 层,即距离原点 0 的距离为 l

由于只需要遍历数组一次,所以这种方案的时间复杂度为 $\O(n)$;而额外空间复杂度只有 $\O(1)$。

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        level = 0
        firstInLevel, lastInLevel = 0, 0
        while True:
            lastInNextLevel = -1
            for j in range(firstInLevel, lastInLevel+1):
                lastInNextLevel = max(lastInNextLevel, j + nums[j])
            if lastInNextLevel >= len(nums) - 1:
                # dest is in next level
                return level + 1
            level += 1
            firstInLevel = lastInLevel + 1
            lastInLevel = lastInNextLevel
        return level
You’ve successfully subscribed to Skyward
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.
Your link has expired
Success! Check your email for magic link to sign-in.