Time Limit Exceeded. Any suggestions?


  • 0
    X

    I used an auxiliary array to keep the minimum steps to reach each index. I think this should be a DP solution. However, it exceeded the time limit. Any suggestion to improve my algorithm? Thanks in advance!

    class Solution:
        # @param A, a list of integers
        # @return an integer
        def jump(self, A):
            #use an auxiliary array to keep the min steps to reach each index
            if len(A) <= 1:
                return None
            aux = [None for x in A]
            aux[0] = 0
            i = 0
            while aux[i] != None:
                for j in range(A[i], 0, -1):
                    if i+j >= len(A)-1:
                        return aux[i]+1
                    elif aux[i+j] == None:
                        aux[i+j] = aux[i] + 1
                i += 1
            return aux[-1]

  • 0
    public  int jump(int[] A)
    {
    	int times = 0;
    	
    	if(A.length <= 1)
    		return 1;
    	
    	times = recurse(A,A.length - 1,0);
    	
    	return times;
    }
    
    
    
    public int recurse(int[] A,int endIdx,int times)
    {
    	if(endIdx == 0)
    		return times;
    	for(int i = 0;i < endIdx;i++)
    	{
    		if(i + A[i] >= endIdx)
    		{
    			endIdx = i;
    			times += 1;
    			return recurse(A,endIdx,times);
    
    		}
    	}
    	
    	return 0;
    }

Log in to reply
 

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