Thursday, August 11, 2011

Jump or not jump (solution)

Given an array start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when u reach the goal in minimum number of jumps.
For ex:
Given array A = {2,3,1,1,4}
possible ways to reach the end (index list)
i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index 4)
ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)


This problem smells like a good candidate for Dynamic Programming. One additional observation is that you need to start processing from right to left for solving the problem. Given the example:

min[4] = 0 (because you are at the end)
min[3] = 1 (because you can just go right of 1 position, more than that will be not allowed)
min[2] = min (min[4], min[3]) here you need to consider all the one that are effectively reachable from current position and this is expressed by current index.

Now how can you get this minimum for a given interval?

a) checking all the positions -> will give you a quadratic algorithm
b) using a tree -> insert and get minimum will give you an O(n log n) algorithm
c) using range queries or Range mimimum queries and this is linear because the minimum for an internal can be obtained in O(1)

1 comment:

  1. A Dynamic Programming solution working in O(n^2).