Solving Jump Game problems on leetcode

Jump Game — Medium

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Solution:

An index i is reachable only if there is a way to reach index “i-1” and the jump length of index “i-1” is ≥1. So, we traverse through the array and update the positions with the maximum value that can be reached from that particular position and for an index i, if i-1 cannot be reached or the jump length of i-1=0,then we can’t reach index i.

Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

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

You can assume that you can always reach the last index.

Jump Game III

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Jump Game IV

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

• i + 1 where: i + 1 < arr.length.
• i - 1 where: i - 1 >= 0.
• j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Solution: Think of it as a bfs problem. In bfs, we visit all elements reachable from a particular node and append it to the queue. Similarly, here we append all the elements which are reachable from a particular element and append it to the queue and if the index of element popped from queue equals len(arr)-1,then we reached the last element and hence return the number of jumps. If you know how to print level order of tree by each level, then the solution should be pretty striaght forward.

“Know how to print the level order of tree level-wise i.e printing all elements in each level in a line. If you know it, then Jump game Iv can be easily solved.”