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

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));

``````