# Jump Game Coding Interview Question

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

#### 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

``````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;
}

// Driver Code
const arr = [ 1, 3, 6, 1, 0, 9 ];
const size = arr.length;
console.log(minJumps(arr, size));

``````