Why my Java O(n^2) solution get TLE?


  • 1
    X
    public static boolean canJump(int[] A) {
        if(A[0]==0){
        	return false;
        }
    	boolean[] chart=new boolean[A.length];
        int n=A.length;
        chart[n-1]=true;;
        for(int i=A.length-2;i>=0;i--){
        	for(int j=i;j<A.length;j++){
        		if(A[i]>=j-i && chart[j]){
        			chart[i]=true;
        		}
        	}
        }
        return chart[0];
    }

  • 1
    S

    Take a look at this solution. The best solution shouldn't be O(n^2).


  • 0
    S

    How about this?

    if(A[i]>=j-i && chart[j]){
    chart[i]=true;
    break;
    }


  • 0
    T

    It's because you assign true to some of the array element too many times when the input is large. If you keep a variable who stores index of the furthest true from the end of the array you have right now, and omit unnecessary assignments, it'll get accepted.

    As mentioned in other posts, there are better solutions in O(n).


Log in to reply
 

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