Learning Journal

2/23/2024

Jump Game - Greedy approach

function canJump(nums: number[]): boolean {
    
    let curI = 0;
    let endRangeI = curI + nums[curI];

    while(endRangeI < nums.length) {
        if(curI === nums.length - 1) return true;
        else if (nums[curI] === 0) return false;

        let nextI = curI + 1, maxRange = nextI + nums[nextI];

        for(let i = nextI + 1; i <= endRangeI; i++) {
            if(maxRange <= i + nums[i]){
                maxRange = i + nums[i];
                nextI = i;
            }
        }
        


        curI = nextI;
        endRangeI = curI + nums[curI];
    }

    return true;
};
function canJump(nums: number[]): boolean {
    
    let curI = 0;
    let endRangeI = curI + nums[curI];

    while(endRangeI < nums.length) {
        if(curI === nums.length - 1) return true;
        else if (nums[curI] === 0) return false;

        let nextI = curI + 1, maxRange = nextI + nums[nextI];

        for(let i = nextI + 1; i <= endRangeI; i++) {
            if(maxRange <= i + nums[i]){
                maxRange = i + nums[i];
                nextI = i;
            }
        }
        


        curI = nextI;
        endRangeI = curI + nums[curI];
    }

    return true;
};

THE PROBLEM

This is the greedy approach for the Jump Game problem. Previously, my approach was to go from the end back to the beginning. For each element, I will check if it can jump to the last "good" node. The "good" node is the node from which we can jump to the end. To check if we can jump from the current position to the "good" node, we add the current index to the number of maximum steps (that was stored in the element at current index) that we can jump from this index. If the total is greater than the index of the "good" node, which means we can jump further than the "good" node, which means the "good" node is within reach. So, we mark the current index as the last index of the "good" node, then, we move to the next element. Doing this way, we need to check all elements, one by one.

However, we can improve even further. Instead of going from the end, we can go from the beginning, and we start to jump. First, we find the current range, which spreads from the current index to n steps further to the right in which n is the value stored on the element at the current index. Then, we find within that range, which element that from it we can jump the furthest and make that element our next node. Then, we do it again until we go pass the end of the array. If we can go pass the end of the array, it means we can reach the end. The only reason that we fail is that there is some 0-step element on the way and there is no way that we can go pass this element.

Revised by ChatGPT

This is a greedy approach to the Jump Game problem. In a previous approach, I worked backward from the end to the beginning, checking if each element could jump to the last "good" node (a node from which the end can be reached). If the sum of the current index and the maximum jump length stored in that element is greater than the index of the "good" node, the current index becomes the new "good" node. This method requires checking each element individually.

However, we can optimize this by moving forward from the beginning. We establish a current range from the current index to n step ahead, where n is the value at the current index. Within this range, we find the element that allows us to jump the furthest and make it our next node. We repeat this process until we pass the end of the array, indicating that the end is reachable. The only failure case is encountering a 0-step element that cannot be bypassed within the current range.

This approach is correct because it effectively utilizes the greedy algorithm principle to solve the Jump Game problem. Here's why it works:

Local Optimum Leads to Global Optimum: At each step, you choose the next position that allows you to jump the furthest. This local optimum choice ensures that you are always making the most progress towards the end with each jump, which ultimately leads to the global optimum solution of reaching the end or determining that it's not possible.
Progression Guarantee: By always choosing the furthest reachable position within the current range, you guarantee that you are making progress towards the end. If there is a way to reach the end, your approach will find it.
Failure Detection: The only scenario where you can't reach the end is when you encounter a 0-step element, and there's no way to bypass it within the current range. Your approach correctly identifies this situation by checking if the maximum range doesn't extend beyond the current position, which means you are stuck and can't reach the end.
Efficiency: Instead of checking every possible path or going backwards from the end, your approach moves forwards and makes decisions based on the current situation. This reduces unnecessary computations and makes the algorithm more efficient.

Overall, your approach correctly applies the greedy algorithm strategy to make the most progress towards the end at each step, ensuring that you either reach the end or correctly identify that it's impossible.