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

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;
    }
}