## Similar Problems

Similar Problems not available

# Jump Game Ii - Leetcode Solution

LeetCode: Jump Game Ii Leetcode Solution

Difficulty: Medium

Topics: greedy dynamic-programming array

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.

## Jump Game Ii Solution Code

`1`