Fastest algorithm to hop through an array

Start with an array A of positive numbers. Start at index 0. From index i, you can move to index i+x for开发者_StackOverflow社区 any x <= A[i]. The goal is to find the minimum number of moves needed to get to the end of the array.

Here's an example:

{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 

If you always go as far as possible in each move, then this is what you get:

0 , 2 , 3 , 5 , 7

This takes 4 moves. But you can get through it faster by doing it this way

0 , 1 , 4 , 7

This only takes 3 moves.

I thought about this for a bit and did the first thing I thought of, but after thinking for a few more days, I still don't know how to do it any better.

Here's my idea. Start at the end of the array and keep track of the minimum number of moves from some position to the end. So for the example, moves[7] = 0 because it's the end already. Then moves[6] = 1 because it takes one move to get to the end. My formula is

moves[i] = 1 + min(moves[i+1], moves[i+2], ... , moves[i+A[i]])

By the time I get to the beginning, I know the number of moves.

So this is O(n^2) which is okay I guess, but probably there is a faster way?

Since you can chose any x in [1,A[i]] I guess there is a pretty simple solution :

start at 0:

select the next reachable element from which you can reach the farther element. i.e chose i that maximize i+A[i+x] for x in [1,A[i]]

until you arrive at the end of the list.

Example:

{2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}

start at 0

from 0 you can get to 1 or to 2:

• from 1 you can get to 4
• from 2 you can get to 3

therefore max(0+A[0+x]) is for i = 1

chose 1 from 1 you can get to 2 3 4:

• from 4 you can get to 7
• from 3 you can get to 5
• from 2 you can get to 3

therefore max(1+A[1+x]) is for i = 4

chose 4

you can reach 7

stop

the resulting list is : 

0,1,4,7

As explained in my comments I think it's O(N), because from i you reach i+x+1 in at least 2*x operations.

'Pseudo' proof

You start at 0 (it's optimal)

then you select i that maximize(0+A[0+x]) (i.e that maximize the reachability for the next element)

from that i you can reach any other element that is reachable from all other elements reachable from 0 (it's a long sentence, but it means : who can do more, can do less, therefore if i is not optimal,it's as good as optimal)

So i is optimal

then following step by step this reasoning, it proves the optimality of the method.

If someone knows how to formulate that more mathematically, feel free to update it.

Treat the array of numbers as a graph and then the problem is equivalent to the Shortest Path Problem, which can be solved in O(|E|+|V|log|V|) time using Dijkstra's algorithm.

E = ∑ of the numbers.

V = # of numbers.

Use your basic idea, but start from the beginning instead and you can get O(n).

The goal is to make a sequence (A_i1, A_i2, ..., A_ik, ...) such that

1. positions 0,1,2,...,ik can be reached in k or fewer steps

2. positions i(k-1)+1, i(k-1)+2, ..., ik cannot be reach in fewer than k steps

The base case is easy:

i0 = 0
i1 = A[0]

and the inductive part isn't too complicated:

i(k+2) = max { A_(ik+1) + ik , A_(ik+1) + ik+1, ..., A_(i(k+1)) + i(k+1) }

I'll go against the flow and tell you that your algorithm is "perfect".

It uses dynamic programming in its cleanest form, and its complexity is not so bad. In this sense, I'd say it is likely to be what was expected from you at the interview.

If you have a bound on the entries (say A[i] <= C(N)), then its complexity is O(N * max(C(N), N)). For instance, if all the entries are less than K, it is O(N).

Using Dijkstra's algorithm (or more generally reducing the problem to a shortest path problem) is smart, but I rank it behind the clean DP solution, since graph algorithms are complex (and it could backfire at an interview if you were asked about them).

Note that Dijkstra would be O(N C(N) + N log N) instead (N vertices, and N C(N) edges). So depending on C, you are either strictly better or equal in complexity.

You could formulate it as a graph algorithm (really, what problem can't be?). Let the positions in the array be the vertices, and the possible destinations have an edge from each vertex. In your example, vertex 0 would have edges to 1 and 2, while vertex 1 would have edges to 2, 3, 4 and 5.

There are several efficient graph search algorithms. For instance, Dijkstra's is O(|E| + |V|log|V|), and A* is O(log h*), which is better if you can come up with a good heuristic.

You can convert the array into a graph and find the shortest path. Here is how the transformation from array to graph should work.

Each array element is an node. And, based on the value in the array element a edge to drawn between the node to the other indices(nodes) we can jump to. Once we have this graph we can find shortest path, which is better than O(n^2).

http://i.imgur.com/Ih3UP.png

My naive approach - going from the start, doing breath-first through all paths ( child nodes are A[i+1] .. A[i+n] ), saving found paths yo some array and then get the shortest paths. Of course all indexes i+n > length(A) are discarded. So it's upper bound is O(n*min(n,max(A[i=0..n])) + n) - in should less than quadratic in practice.

Dynamic programming solution:

keep track for each element the smallest number of steps you can get there and from where you came. then just simply walk through the array and for each element update the available next positions (from i+1 till i+a[i]).

{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 
  0

{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 
  0   1   1 (num of steps)
      0   0 (source)
  ^         (current position)
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 
  0   1   1   2   2   2
      0   0   1   1   1
      ^
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 
  0   1   1   2   2   2
          ^
etc...

This is O(n+sum(a[i])) .. or a bit less, you don't have to go beyond the boundary of the array.

Here's a slight modification of Ricky Bobby's answer, which I'll show to be optimal:

find_shortest_path(A):
    path := [0]
    last := 0
    max_reachable = 0

    while A[last] + last < length(A) :  
        next_hop := x such that max_reachable < x <= A[last] + last and last + A[x] is maximum
        push(path, x)
        max_reachable = A[last] + last
        last := x

    return path

proof of correctness: I'll use induction the nodes of the path created by my algorithm.

the property I'll show is P(i) = the ith node of my path has a 'reach' no smaller than the ith node of any optimal path

where reach is defined as the number of the highest node you can hop to from that node, or +infinity if you can get past the end of the array

P(0) is obvious.

assume that P(k) is true for k >= 0

now consider the (k + 1)th node in the path created by my algorithm. Since my algorithm chose node k so that it had at least the same reach as that of the optimal path's node k, the set of nodes which may possibly be the (k + 1)th node for my algorithm is a superset of the same for any optimal path. Since my algorithm chooses the node with the greatest reach, it follows that P(K + 1) is true.

by induction, P(k) is true for all k (up to the size of the path created).

since my algorithm will end as soon as the end of the array is in reach, and this will happen no later than for any optimal path, it follows that the path created by my algorithm is optimal.

proof of optimality: each cell of the array is considered at most once, so it's O(n), which is asymptotically optimal. I don't think it's possible to design an algorithm which checks fewer cells in every case.

My method: Create an array reqSteps to store the number of moves an input takes to escape.
Start from the end of the array.
Check if input[i] can escape the array by itself, if yes enter 1 in minSteps, if no, store the minimum of successive input[i] values + 1. Result is minSteps[0];
The top method does not work for the input{ 10, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1 };
It will give 9 as the answer.
Correct answer is 2.

public static void arrayHop()
{
        int[] input = { 10, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1 };
        int length = input.length;
        int answer = calcArrayHop(input, length);

}

public static int calcArrayHop(int[] input, int length) {
    int minSteps;
    int[] reqSteps = new int[length];
    for(int i=0;i<length;i++)
        reqSteps[i]=Integer.MAX_VALUE;
    int nextStep;

    for (int i = length - 1; i >= 0; i--) {
        int minsteps = Integer.MAX_VALUE;
        if (i + input[i] >= length) {
            reqSteps[i] = 1;
        } else
        {
            for (int j = i+1; j <= (i + input[i]); j++) {
                if(j>input.length-1)
                    break;
                if (reqSteps[j] < minsteps)
                    minsteps = reqSteps[j];
            }
        reqSteps[i] = minsteps+1;
        }


    }

    return reqSteps[0];
}

}