Jump Game Ii - Leetcode Solution

Problem:

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2:

Input: nums = [2,3,0,1,4] Output: 2

Approach:

This problem can be solved using the BFS algorithm. The idea is to create a graph where each node represents an index in the array and the edges represent the valid jumps from that index. We will do a BFS traversal from the first index and stop when we reach the last index.

For this, we need to maintain a queue of pairs (index, jumps) where index represents the current index and jumps represents the number of jumps taken to reach this index. Initially, we will push the pair (0,0) into the queue.

In the BFS traversal, we will consider all the valid jumps from the current index and push the corresponding pairs into the queue. We will also mark the current index as visited so that we do not consider it again.

We will continue this process until the queue is empty. At the end of the traversal, we will return the jumps required to reach the last index.

Solution:

Here is the Python implementation of the above approach:

from collections import deque

class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) if n == 1: return 0

    # create a graph
    graph = [[] for _ in range(n)]
    for i in range(n):
        for j in range(1, nums[i]+1):
            if i+j >= n:
                break
            graph[i].append(i+j)

    # BFS traversal
    queue = deque()
    visited = set()
    queue.append((0,0))
    visited.add(0)
    while queue:
        index, jumps = queue.popleft()
        for v in graph[index]:
            if v == n-1:
                return jumps + 1
            if v not in visited:
                queue.append((v, jumps+1))
                visited.add(v)

The time complexity of this solution is O(n^2) because we are creating a graph by iterating over all the possible jumps from each index. However, we can optimize the solution by using a greedy approach.

We can maintain two pointers, start and end, where start represents the starting index of the current jump and end represents the ending index of the current jump. We will consider all the indices between start and end and find the index that can lead to the farthest jump.

Once we find the index that can lead to the farthest jump, we will update the end pointer to that index and increment the jumps required to reach that index. We will continue this process until we reach the last index.

Here is the Python implementation of the optimized approach:

class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) if n == 1: return 0

    start, end = 0, 0
    jumps = 0
    while end < n-1:
        jumps += 1
        farthest = end
        for i in range(start, end+1):
            if i + nums[i] >= n-1:
                return jumps
            farthest = max(farthest, i+nums[i])
        start, end = end+1, farthest

    return jumps

The time complexity of this solution is O(n) because we are iterating over the array only once.

1