Jump Game Coding Interview Question

Jump Game Coding challenge. You may be asked this type of coding challenges during onsite interview.

You have been given an array ‘ARR’ of ‘N’ integers and you have to find the minimum number of jumps needed to reach the last index of the array i.e ‘N – 1’ if at any index ‘i’ we can jump to an index ‘i + k’ such that 1<= ‘k’ <= ARR[i] i.e the element you are currently at represents the maximum distance you can jump from the current element.

Our goal is to reach the last index in the minimum number of jumps.

Assume that, under the given constraints, you can always reach the last index.

Problem Note:

If it is not possible to reach the last index, return -1.

If an element is 0, then you cannot move through that element.

Example 1 Input: arr[] = [2, 1, 1] Output: 1 Explanation: The minimum number of jumps to reach the last index is 1. Jump 2 steps from index 0 to 2.

Example 2 Input: arr[] = [2, 3, 2, 4, 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.

Solutions

1. Brute Force Solution → We will start with the ‘0’th index and try all options. So for this Example [2,1,1] => we can go from 2 to last index directly or from 2=> 1 and then last index. Then we will return “1” as minimum jumps. But that won’t be an ideal solution.
2. Dynamic Programming → For each value at the ith index, move from ith index to ith+ar[i] and update the minimum number of jumps till there.
3. Optimized Dynamic Programming

Read More on Most Frequently Asked Interview Questions & Answers.

const minJumps = (arr, n) => {
  let jumps = Array.from({length: n}, (_, i) => 0);
  let min;
 
    // Minimum number of jumps
    // needed to reach last
    // element from last elements
    // itself is always 0
    jumps[n - 1] = 0;
 
    // Start from the second
    // element, move from right
    // to left and construct the
    // jumps array where jumps[i]
    // represents minimum number of
    // jumps needed to reach arr[m-1]
    // from arr[i]
    for (let i = n - 2; i >= 0; i--) {
        // If arr[i] is 0 then arr[n-1]
        // can't be reached from here
        if (arr[i] == 0)
            jumps[i] = Number.MAX_VALUE;
 
        // If we can directly reach to
        // the end point from here then
        // jumps[i] is 1
        else if (arr[i] >= n - i - 1)
            jumps[i] = 1;
 
        // Otherwise, to find out
        // the minimum number of
        // jumps needed to reach
        // arr[n-1], check all the
        // points reachable from
        // here and jumps value
        // for those points
        else {
            // initialize min value
            min = Number.MAX_VALUE;
 
            // following loop checks
            // with all reachable points
            // and takes the minimum
            for (j = i + 1; j < n && j <= arr[i] + i; j++) {
                if (min > jumps[j])
                    min = jumps[j];
            }
 
            // Handle overflow
            if (min != Number.MAX_VALUE)
                jumps[i] = min + 1;
            else
                jumps[i] = min; // or Number.MAX_VALUE
        }
    }
 
    return jumps[0];
}
 
// Driver Code
const arr = [ 1, 3, 6, 1, 0, 9 ];
const size = arr.length;
console.log(minJumps(arr, size));