Jump Game - I - AlgoArena Witeso

Intuition

Keep track of the farthest position that can be reached at any point. If at an index where it's impossible to move to the next one because it's too far away, then it's impossible to get to the end, and the process must stop. Otherwise, continue updating the farthest reachable index while moving forward. If the traversal manages to reach or pass the last index, then reaching the end is possible.

Approach

Start by setting a pointer to track the farthest point that can be reached from the beginning of the array.
Iterate through each position in the array, checking if the current position exceeds the farthest point reached so far.
If the current position is beyond the reachable point, it indicates that further progress is not possible, and reaching the end is infeasible.
If the current position is within the reachable point, update the pointer to reflect the farthest position that can be reached from the current spot.
If the entire array is traversed without finding an unreachable position, it confirms that the last index is reachable, thus making it possible to reach the end.

Dry Run

Possible to Reach

Not possible to Reach

Solution

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    // To determine if last index is reachable
    bool canJump(vector<int>& nums) {
        // Initialize maximum index
        int maxIndex = 0;

        // Iterate through each index of the array
        for (int i = 0; i < nums.size(); i++) {
            /*If the current index 
            is greater than the 
            maximum reachable index
            it means we cannot move 
            forward and should 
            return false*/
            if (i > maxIndex) {
                return false;
            }

           /* Update the maximum index that can be 
           reached by comparing
            the current maxIndex with the sum 
            of the current index and
            the maximum jump from that index*/
            maxIndex = max(maxIndex, i + nums[i]);
        }

       /* If we complete the 
       loop, it means we 
       can reach the 
       last index*/
        return true;
    }
};

int main() {
    vector<int> nums = {4, 3, 7, 1, 2};

    cout << "Array representing maximum jump from each index: ";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    Solution solution;
    bool ans = solution.canJump(nums);

    if (ans) {
        cout << "It is possible to reach the last index." << endl;
    } else {
        cout << "It is not possible to reach the last index." << endl;
    }

    return 0;
}
import java.util.*;

class Solution {
    // To determine if last index is reachable
    public boolean canJump(int[] nums) {
        // Initialize maximum index
        int maxIndex = 0;

        // Iterate through each index of the array
        for (int i = 0; i < nums.length; i++) {
            /* If the current index 
               is greater than the 
               maximum reachable index
               it means we cannot move 
               forward and should 
               return false */
            if (i > maxIndex) {
                return false;
            }

            /* Update the maximum index that can be 
               reached by comparing
               the current maxIndex with the sum 
               of the current index and
               the maximum jump from that index */
            maxIndex = Math.max(maxIndex, i + nums[i]);
        }

        /* If we complete the 
           loop, it means we 
           can reach the 
           last index */
        return true;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 7, 1, 2};

        System.out.print("Array representing maximum jump from each index: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();

        Solution solution = new Solution();
        boolean ans = solution.canJump(nums);

        if (ans) {
            System.out.println("It is possible to reach the last index.");
        } else {
            System.out.println("It is not possible to reach the last index.");
        }
    }
}
class Solution:
    # To determine if last index is reachable
    def canJump(self, nums):
        # Initialize maximum index
        max_index = 0

        # Iterate through each index of the array
        for i in range(len(nums)):
            # If the current index is greater than the 
            # maximum reachable index it means we cannot move 
            # forward and should return false
            if i > max_index:
                return False

            # Update the maximum index that can be 
            # reached by comparing the current maxIndex with the sum 
            # of the current index and the maximum jump from that index
            max_index = max(max_index, i + nums[i])

        # If we complete the loop, it means we can reach the last index
        return True

# Example usage
if __name__ == "__main__":
    nums = [4, 3, 7, 1, 2]

    print("Array representing maximum jump from each index: ", end="")
    for num in nums:
        print(num, end=" ")
    print()

    solution = Solution()
    ans = solution.canJump(nums)

    if ans:
        print("It is possible to reach the last index.")
    else:
        print("It is not possible to reach the last index.")
class Solution {
    // To determine if last index is reachable
    canJump(nums) {
        // Initialize maximum index
        let maxIndex = 0;

        // Iterate through each index of the array
        for (let i = 0; i < nums.length; i++) {
            /* If the current index 
               is greater than the 
               maximum reachable index
               it means we cannot move 
               forward and should 
               return false */
            if (i > maxIndex) {
                return false;
            }

            /* Update the maximum index that can be 
               reached by comparing
               the current maxIndex with the sum 
               of the current index and
               the maximum jump from that index */
            maxIndex = Math.max(maxIndex, i + nums[i]);
        }

        /* If we complete the 
           loop, it means we 
           can reach the 
           last index */
        return true;
    }
}

// Example usage
const nums = [4, 3, 7, 1, 2];

console.log("Array representing maximum jump from each index: " + nums.join(" "));

const solution = new Solution();
const ans = solution.canJump(nums);

if (ans) {
    console.log("It is possible to reach the last index.");
} else {
    console.log("It is not possible to reach the last index.");
}

Complexity Analysis

Time Complexity: O(N) where N is the length of the array. We iterate through the input array exactly once and at each element perform constant time operations. Space Complexity: O(1) no extra space used.

Problem List

Jump Game - I

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code