CareerCup

I think one way of doing it is by building a DAG. Have a DAG with each node representing each index of the array. So for array of size 'n' you'd get a DAG with 'n' nodes. Now connect the nodes which are reachable from each node. i.e. if A[i]=k then make directed edges from node representing 'i' to nodes i+1, i+2 ... i+k. Once you have built the graph, a simple BFS would fetch u the shortest path as well as the number of nodes in the path.

O(n) is possible.

Start from the left. You always have a sub-array A[0], A[1], ..., A[n_k] which is reachable in k or less steps.

i.e. A[0], A[1], .., A[n_1] is reachable after 1 step.

A[0], A[1], ..., A[n_2] is reachable in 1 or 2 steps, with A[n_1+1],..., A[n_2] being reachable only in 2 steps.

So to compute n_{k+2}, you simply consider max {A[n_k+1] + n_k , A[n_k+1], n_k+1, ..., A_[n_{k+1}] + n_{k+1}}

Since you consider each element A[j] only once, this is an O(n) time algorithm.


The O(n log n) time algorithm described is interesting. It computes the shortest path for each element!

Kind of like a single shortest path vs all pairs shortest path.

Dynamic programming.
Start from the right.

This is possible in O(n^2) using DP. If this complexity is acceptable, I will explain.

public final class OptimalJump {
	
	public OptimalJump(int[] arr) {
		super();
		this.arr = arr;
	}
	
	
	public Jump determineJump(){		
		return findMinJump(0, 0);
	}
	
	
	//==== NESTED ====
	
	public static class Jump implements Comparable<Jump> {

		@Override
		public int compareTo(Jump other) {
			
			int size1 = elements.size();
			int size2 = other.elements.size();
						
			if( size1 > size2 ){
				return 1; 
			}
			else if( size1 < size2 ){
				return -1;
			}
			
			return 0;
		}
		
		@Override
		public String toString(){			
			return elements.toString();
		}
		
		private List<Integer> elements = new ArrayList<Integer>();
	}
	
	private static final class JumpKey {
		
		
		JumpKey(int index, int offset) {
			super();
			this.index = index;
			this.offset = offset;
		}
		
		int index;
		int offset;
		
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + index;
			result = prime * result + offset;
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			JumpKey other = (JumpKey) obj;
			if (index != other.index)
				return false;
			if (offset != other.offset)
				return false;
			return true;
		}
		
		
	}
	
	//==== PRIVATE ====
	
	private final int[] arr;

	private final Map<JumpKey, Jump> cache = new HashMap<JumpKey, Jump>();
		
	
	private Jump findMinJump( int index, int offset ){
		
		final JumpKey key = new JumpKey(index, offset);		
		Jump memJump = cache.get( key );
		
		if( memJump != null ){
			return memJump;
		}
		
		index = index + offset;
		
		final int value = arr[index];
		
		Jump minJump = null;
		
		for( int i = 1; i < value+1 && index+i < arr.length; i++ ){
			
			Jump jump = findMinJump(index, i);
			
			if( minJump == null || jump.compareTo(minJump) < 0 ){
				minJump = jump;
			}
		}
		
		if( minJump == null ){
			minJump = new Jump();
		}
		
		minJump.elements.add(0, index);
		cache.put(key, minJump);
		
		return minJump;		
	}
	

}

Let arraylength = N
keep mincount = N, patharray[N], minpatharray[N]
function jump (arr, int i, count)
{
  if (i equals N)
  {
     check current patharray.     
     if count < mincount 
     {
      save a copy of current patharray in minpatharray
      mincount = count;
     }
  }
  else
    patharray[count++] = i;

  for (j=1 to N)
   jump (arr, i+j, count);
}

call jump as 
jump (arr, 0, 0);
print minpatharray and mincount.

correction in previous code
for (j=1 to arr[i])
   jump (arr, i+j, count);

tech-queries.blogspot.com/2011/08/find-optimal-number-of-jumps-to-reach.html

I think its Dijkstra where:
1. Adjacent vertices are all values at the index <= (current index+current value)
2. distance is the value at indices
3. weight is constant
4. Instead of min we have to extract max while doing BFS.

As we know that using priority heap it can be done in nlogn

Please correct me if my approach is wrong.

#include <iostream>
using namespace std;

int select_max(int arr[], int current_pos, int max_pos);

int main()
{
  int arr[] = {3,3,2,2,4,8,2,1,10,9,5,2};
  int jumps = 0;
  int size = (int)(sizeof(arr)/sizeof(int));
  for(int i = 0; i + arr[i] < size - 1;)
  {
     i = select_max(arr, i, i + arr[i]);
     cout << "jump to " << i <<  "\n";
     jumps++;
  }
  cout << "Number of jumps = " << jumps << endl;
}

int select_max(int arr[], int current_pos, int limit_pos)
{
  int max_pos = current_pos;
  int max_value = 0;
  for(int i = current_pos; i <= limit_pos; ++i)
  {
    if(arr[i] >= max_value)
    {
      max_pos = i;
      max_value = arr[i];
    }
    
    max_value--;
  }

return max_pos;
}

Did I miss anything?

@Nitin : Your approach will fail for sequence as below :
10,9,8,7,6,4,3,2,1,1,1..
when you are at 10, your algo with select 9 as next index to be used, although the current jump of 10 itself is good enough to move 10 steps ahead.

@Nitin : Your approach will fail for sequence as below :
10,9,8,7,6,4,3,2,1,1,1..
when you are at 10, your algo with select 9 as next index to be used, although the current jump of 10 itself is good enough to move 10 steps ahead.

<pre lang="" line="1" title="CodeMonkey19107" class="run-this">@Nitin : Your approach will fail for sequence as below :
10,9,8,7,6,4,3,2,1,1,1..
when you are at 10, your algo with select 9 as next index to be used, although the current jump of 10 itself is good enough to move 10 steps ahead.</pre>

@Nitin. Your approach fails for below input sequence :-
5,1,2,3,4,1,1,1,5,1,1,2,E

Intially your algo with select index 0 among 5,1,2,3,4 values. Thus from 0 you will go to index 5 having value 1. but instead of chosing index 0 you would hv choosen index 4 having value 4, then from index 4 you would hv got option of moving to index 8 having value 5, which will take u to end.

According to your algo :- 5,1,1,1,5,E
But the best solution is :- 5,4,5,E

Similar to Djikstra
1. each ith element(or node) is connected to next a[i] elements(nodes)
2. Distance between any 2 nodes is 1
3. solution : shortest distance between a[0] and a[n-1]

MJ(i)
	if(i == n)
		return 0
	min = 0
	for each j from i+1 to i +a[i]
		 v = MJ(a[j])+1
		if(v < min)
			min = v
	return min

A simple linear time solution.

public boolean canJump(int[] A) {
        if(A.length <= 1) return true;
        
        // the small index position that can jump to the end
        int firstJump = A.length-1;
        for(int i=A.length-2;i>=0;i--){
            int j = i+A[i];
            if(j >= A.length-1 || j>=firstJump){
                firstJump=i;
                break;
            }
        }
        
        return firstJump == 0;
    }