Time Limit Exceeded. Help.


  • 1
    D
    public int jump1(int[] A) {
        // steps[i] = min { steps[j] } + 1, j <= i + A[i]
    	int[] steps = new int[A.length];
    	for(int i = A.length - 2; i >= 0; i--) {
    		int curMin = steps[i+1];
        	for(int j = i + 1; j < A.length && j <= i + A[i]; j++)
        		if(steps[j] < curMin) curMin = steps[j];
        	steps[i] = curMin + 1;
    	}
    	return steps[0];
    }

  • 3
    D

    Actually, your idea of using dynamic programming is fine, except that it takes too much time.

    If you keep looking for another solution, you will see that it is actually like a graph problem: find the length of the shortest path from the start node to the end node (each node in the graph is corresponding to an element of the array A. and an edge from B->C if from B can jump to C).

    Based on this, we can have the following code (for your reference).
    Suggestion: when u go from backward of an array and get time limited error, try to go from the start of the array.

    public class Solution {
        public int jump(int[] A) {
            int [] jumps = new int[A.length];
            for(int i = 1; i<A.length; i++)
                jumps[i] = Integer.MAX_VALUE;
            int current = 0;
            int fast = 1;
            
            while(fast < A.length && current<A.length){
            
                int maxJump = A[current];
                for(int i = fast; i <= current+maxJump && i<A.length; i++){
                    if(jumps[current] + 1 < jumps[i])
                        jumps[i] = jumps[current] + 1;
                }
                if(fast < current+maxJump)
                    fast = current+maxJump;
                current++;
                
            }
            return jumps[A.length-1];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.