Jump Game Ii

                                            
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int jumps = 0;
        int curEnd = 0;
        int curFarthest = 0;

        for (int i = 0; i < n - 1; i++) {
            curFarthest = max(curFarthest, i + nums[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }

        return jumps;
    }
};

                                            
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }
        
        int jumps = 0, curEnd = 0, curFarthest = 0;
        
        for (int i = 0; i < n - 1; i++) {
            curFarthest = Math.max(curFarthest, i + nums[i]);
            
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }
        
        return jumps;
    }
}

                                            
class Solution(object):
    def jump(self, nums):
        n = len(nums)
        if n == 1:
            return 0
        
        jumps = 0
        cur_end = 0
        cur_farthest = 0
        
        for i in range(n-1):
            cur_farthest = max(cur_farthest, i + nums[i])
            if i == cur_end:
                jumps += 1
                cur_end = cur_farthest
                if cur_end >= n-1:
                    break
        
        return jumps

                                            
int jump(int* nums, int numsSize) {
    int jumps = 0;
    
    int currentJumpEnd = 0;
    int farthestJump = 0;
    
    for (int i = 0; i < numsSize - 1; i++) {
        farthestJump = (i + nums[i] > farthestJump) ? i + nums[i] : farthestJump;
        
        if (i == currentJumpEnd) {
            jumps++;
            currentJumpEnd = farthestJump;
        }
    }
    
    return jumps;
}

                                            
public class Solution {
    public int Jump(int[] nums) {
        int n = nums.Length;
        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;
        
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.Max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }
        
        return jumps;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if (nums.length === 1) {
        return 0;
    }
    
    let steps = 0;
    let maxReach = nums[0];
    let edge = nums[0];
    
    for (let i = 1; i < nums.length - 1; i++) {
        maxReach = Math.max(maxReach, i + nums[i]);
        
        if (i === edge) {
            steps++;
            edge = maxReach;
        }
    }
    
    return steps + 1;
};

                                            
function jump(nums: number[]): number {
    if (nums.length === 1) return 0;
    
    let jumps = 0;
    let currentJumpEnd = 0;
    let farthest = 0;
    
    for (let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        
        if (i === currentJumpEnd) {
            jumps++;
            currentJumpEnd = farthest;
        }
    }
    
    return jumps;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function jump($nums) {
        $n = count($nums);
        $maxPosition = 0;
        $end = 0;
        $jumps = 0;
        
        for ($i = 0; $i < $n - 1; $i++) {
            $maxPosition = max($maxPosition, $i + $nums[$i]);
            if ($i == $end) {
                $end = $maxPosition;
                $jumps++;
            }
        }
        
        return $jumps;
    }
}

                                            
class Solution {
    func jump(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return 0
        }
        
        var steps = 0
        var maxReach = nums[0]
        var nextReach = nums[0]
        
        for i in 1..<nums.count {
            if i > maxReach {
                steps += 1
                maxReach = nextReach
            }
            
            nextReach = max(nextReach, i + nums[i])
        }
        
        return steps + 1
    }
}

                                            
class Solution {
    fun jump(nums: IntArray): Int {
        if(nums.size <= 1) return 0
        
        var jumps = 0
        var currentEnd = 0
        var farthest = 0
        
        for(i in 0 until nums.size - 1) {
            farthest = maxOf(farthest, i + nums[i])
            
            if(i == currentEnd) {
                jumps++
                currentEnd = farthest
            }
        }
        
        return jumps
    }
}

                                            
class Solution {
  int jump(List<int> nums) {
    if (nums.length <= 1) {
      return 0;
    }
    
    int jumps = 0;
    int currentEnd = 0;
    int farthest = 0;
    
    for (int i = 0; i < nums.length - 1; i++) {
      farthest = i + nums[i] > farthest ? i + nums[i] : farthest;
      
      if (i == currentEnd) {
        jumps++;
        currentEnd = farthest;
      }
    }
    
    return jumps;
  }
}

                                            
func jump(nums []int) int {
    if len(nums) <= 1 {
        return 0
    }

    maxPos := nums[0]
    maxSteps := nums[0]
    jumps := 1

    for i := 1; i < len(nums); i++ {
        if maxSteps < i {
            jumps++
            maxSteps = maxPos
        }
        
        if maxPos < i+nums[i] {
            maxPos = i + nums[i]
        }
    }

    return jumps
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def jump(nums)
    n = nums.length 
    return 0 if n == 1

    jumps = 0
    curr_end = 0
    curr_farthest = 0

    (0..n-2).each do |i|
        curr_farthest = [curr_farthest, i + nums[i]].max

        if i == curr_end
            jumps += 1
            curr_end = curr_farthest

            return jumps if curr_end >= n - 1
        end
    end

    jumps
end

                                            
object Solution {
    def jump(nums: Array[Int]): Int = {
        val n = nums.length
        var jumps = 0
        var currentJumpEnd = 0
        var farthest = 0
        
        for (i <- 0 until n - 1) {
            farthest = Math.max(farthest, i + nums(i))
            if (i == currentJumpEnd) {
                jumps += 1
                currentJumpEnd = farthest
            }
        }
        
        jumps
    }
}

                                            
impl Solution {
    pub fn jump(nums: Vec<i32>) -> i32 {
        let mut jumps = 0;
        let mut current_end = 0;
        let mut farthest = 0;
        
        for i in 0..nums.len() - 1 {
            farthest = farthest.max(i + nums[i] as usize);
            
            if i == current_end {
                jumps += 1;
                current_end = farthest;
            }
        }
        
        jumps
    }
}

To solve this coding challenge, the method we use focuses on tracking the maximum reach and making jumps once reaching the end of the current reachable area. The idea is that we greedily make the optimal jump each time by keeping track of the furthest point that can be reached. We iterate through the list and update our jumps whenever we reach the end of our current range, aiming for the farthest distance possible within the current jump.

Explanation

Initialization : Start by checking if the length of the array is 1, in which case it means we are already at the end and no jump is needed. Initialize variables to keep track of the number of jumps, the current end of the range we can reach, and the furthest point we can reach.
Iterate through the List : Loop through the list, except for the last element as there is no reason to jump from it. In the loop:

Update the furthest point we can reach by comparing the current maximum reachable point with the sum of the current index
i

and its value
nums[i]

.
Check if the current index
i

has reached the end of the current range (the point where we need to make a jump).
Increment the jump counter and update the current end of the range to the furthest point we can reach.

End Condition : If at any point, our current end reaches or exceeds the last element of the list, we break out of the loop as we've determined the necessary jumps.
Return : Finally, return the number of jumps calculated.

Detailed Step-by-Step Explanation

Initialize Essential Variables :

jumps

: Counter to store the number of jumps made, initialized to 0.
current_range_end

: Stores the current end range, initialized to 0.
farthest_point

: Stores the furthest point that can be reached, initialized to 0.

Loop through the Array Except the Last Element :

For each index
i

:

Update
farthest_point

to the maximum of
farthest_point

and
i + nums[i]

.
If
i

equals
current_range_end

, it means we need to jump:

Increment
jumps

by 1.
Update
current_range_end

to
farthest_point

.
If
current_range_end

is greater than or equal to the last index, break out of the loop.

Return the Total Jumps :

Return the
jumps

counter, which now holds the minimum number of jumps to reach the last index.

Detailed Steps in Pseudocode

                                            
function findMinJumps(nums):
    # Get the length of the input array
    length = length of nums
    # If the length of the array is 1, no jumps are needed
    if length is 1:
        return 0

    # Initialize jumps counter to 0
    jumps = 0
    # Initialize the range of the current jump's end position to 0
    current_range_end = 0
    # Initialize the farthest point that can be reached to 0
    farthest_point = 0

    # Loop through each index in the array up to the second last element
    for index from 0 to length - 2:
        # Update the farthest point we can jump to from the current index
        farthest_point = max(farthest_point, index + nums[index])
        
        # Check if the current index is the end of the current range
        if index == current_range_end:
            # Increment the jump counter as we need to make a jump
            jumps = jumps + 1
            # Update the end of the current range to the farthest point we can reach
            current_range_end = farthest_point
            
            # If the current range end reaches or exceeds the last index, break out of the loop
            if current_range_end >= length - 1:
                break

    # Return the total number of jumps calculated
    return jumps

This detailed pseudocode approach outlines how to methodically determine the minimum number of jumps required to reach the last element of the list by always jumping in the way that maximizes the distance within the current jump.