Beyond awesome | 越而胜己

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.

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.