# Solution For Jump Game Ii

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))
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))
``````

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.

## Step by Step Implementation For Jump Game Ii

```class Solution {
public int jump(int[] nums) {
int end = 0;
int maxPosition = 0;
int steps = 0;
for(int i = 0; i < nums.length - 1; i++) {
//找能跳的最远的
maxPosition = Math.max(maxPosition, i + nums[i]);
if( i == end) { //遇到边界，就更新边界，并且步数加一
end = maxPosition;
steps++;
}
}
return steps;
}
}```
```class Solution:
def jump(self, nums: List[int]) -> int:
# Base case: already at the end
if len(nums) == 1:
return 0

# Keep track of the number of jumps needed
# as well as the furthest index that can be reached
jumps, max_reach = 0, nums[0]

# Iterate through the array
for i in range(1, len(nums)):
# If the current index can't be reached, we're done
if i > max_reach:
return -1

# Otherwise, see if this index extends our reach further
max_reach = max(max_reach, i + nums[i])

# If we can reach the end from here, increment the jump count
# and return
if max_reach >= len(nums) - 1:
jumps += 1
return jumps

# If we get here, it means we can't reach the end
return -1```
```var jump = function(nums) {

// keep track of the furthest index we can reach
// as well as the number of jumps it takes to get there
let maxReach = 0;
let jumps = 0;

// iterate through the array
for (let i = 0; i < nums.length - 1; i++) {

// update maxReach if necessary
maxReach = Math.max(maxReach, i + nums[i]);

// if we've reached the end, return the number of jumps
if (maxReach >= nums.length - 1) {
return jumps + 1;
}

// if we can't move any further from our current index,
// we must have made a jump
if (i === maxReach) {
jumps++;
}
}
};```
```class Solution {
public:
int jump(vector& nums) {
int n = nums.size();
if (n <= 1) return 0;
int level = 0, currentMax = 0, i = 0, nextMax = 0;

while (currentMax - i + 1 > 0) {        // nodes count of current level>0
level++;
for (; i <= currentMax; i++) {     // traverse current level , and update the max reach of next level
nextMax = max(nextMax, nums[i] + i);
if (nextMax >= n - 1) return level;   // if last element is in level+1,  then the min jump=level
}
currentMax = nextMax;
}
return 0;
}
};```
```public class Solution {
public int Jump(int[] nums) {
// base case
if (nums.Length <= 1)
{
return 0;
}

// initialize maxPosition and steps
int maxPosition = nums[0];
int steps = nums[0];

// what is the maximum position we can reach
// in at most "steps" jumps
int jumps = 1;

// if not at the end of the array
// keep going
while (maxPosition < nums.Length - 1)
{
// reset steps to 0 so we can
// calculate it again
steps = 0;

// for each position we can reach
// from the previous maxPosition
for (int i = 1; i <= maxPosition; i++)
{
// if it's further than what we've already seen
if (i + nums[i] > steps)
{
// update steps
steps = i + nums[i];
}
}

// update maxPosition and increment jumps
maxPosition = steps;
jumps++;
}

// return the total number of jumps
return jumps;
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]