Jump Game I I Algorithm

The Jump Game II Algorithm is an optimization-based algorithm that solves the classic "jump game" problem. In this problem, a player is given an array of non-negative integers, where each integer represents the maximum jump length at that position. The player's goal is to reach the last index in the minimum number of jumps. The algorithm works by utilizing a greedy approach, focusing on finding the farthest reachable index within the current jump range and updating the jump range as the player moves forward in the array. The key to the Jump Game II Algorithm is to keep track of the current jump range, the farthest reachable index, and the number of jumps required to reach the last index. The algorithm iterates through the input array, updating the farthest reachable index by comparing the current maximum reachable index and the sum of the current index and its corresponding jump length. When the current index reaches the end of the current jump range, the jump range is updated to the farthest reachable index, and the number of jumps is incremented. This process continues until the last index is reached, at which point the algorithm returns the minimum number of jumps required. By focusing on the farthest reachable index and only updating the jump range when necessary, the Jump Game II Algorithm efficiently finds the minimum number of jumps needed to reach the end of the array.
class Solution {
public:
    int jump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int begin = 0, end = 0;
        int min_step = 0;
        int max_next = 0;
        
        while (end < n - 1) {
            min_step += 1;
            for (int i = begin; i <= end; i++)
                max_next = max(max_next, i + A[i]);
            if (max_next <= end) 
                return -1;
            begin = end + 1;
            end = max_next;
        }
        return min_step;
    }
};

LANGUAGE:

DARK MODE: