I am trying to write an efficient algorithm that will find the number of jumps it will take for a pawn to exit an array. Lets say we are given an array, for each element in the array if array[k] = n then array[k] is equal to array[k + n];
For example, we have this array [2,3,-1,1,3].
Initially the pawn is at array[0], on first jump it moves from array[0] to array[2] because 0 + array[0] is equal to 2. on the second jump, the pawn moves from A[2] to A[1] because 2 + A[2] = 1; on the third jump, the pawn moves from A[1] to A[4] because 1 + A[1] = 4; on the fourth jump, the pawn jumps out of the array. It returns 4 for this test case.
If the pawn cant jump out of the array we return -1;
Below is the algorithm I wrote for this problem and it works for a few test cases but fails large test cases. How can I make this algorithm more efficient.
function jumpOut(A) {
let start = 0;
let end = A.length - 1
let pawn = 0;
while (start < end){
pawn= start + A[start]
start++;
}
if(pawn === end){
return pawn
}
return -1;
}
Finding the number of moves required to get out of the array can be done in a linear time if the pawn always jumps EXACTLY the amount specified in the given array.
Before each jump, you can check if the current position of the pawn has been previously visited. If yes, that means there exists a loop that the pawn cannot get out of so return -1. Otherwise keep jumping and return the final count.
function getNumRequiredMoves(jumps) {
// Remember the positions that have been visited
let isVisited = Array(jumps.length).fill(false);
// Position of the pawn
let position = 0;
// Final result
let numMoves = 0;
while (position >= 0 && position < jumps.length) {
if (isVisited[position]) {
// This position has been visited before
return -1;
}
// Mark this position as visited
isVisited[position] = true;
// Jump
position += jumps[position];
// Increment the jump counter
++numMoves;
}
return numMoves;
}
Now at a given time if the pawn can jump anywhere between [1, jumps[position]], you can use dynamic programming to efficiently find the number of required moves.