I use a O(n) recursive method, but I got a TLE, why?


  • 2
    V
    bool recursive(int A[], int n, int curPos, bool *flag){
    	int stride=A[curPos];
    	if(flag[curPos])
    		return false;
    	flag[curPos]=true;
    	if(curPos+stride>=n-1)
    		return true;
    	for(int i=stride;i>=1;i--){
    		if(recursive(A, n, curPos+i, flag))
    			return true;
    	}
    	return false;
    }
    
    bool canJump(int A[], int n){
    	bool *flag=new bool[n];
    	memset(flag, false, sizeof(bool)*n);
    	return recursive(A, n, 0, flag);
    }
    

    In this method I mark the position that has been traversed, and skip the position that has been marked.
    I think this is an O(n) method, but why I got a TLE?


  • 3
    S

    Good question. It may make you think that it is an O(N) algorithm since we are making use of a 1D flag to memoize the intermediate, whereas in reality, it is O(N^2) in the worst case. Think of the following sequence for instance:

    Seq: 5 4 3 2 1 0 100
    
    Ind: 0 1 2 3 4 5 6
    

    Even though the flag array can be filled in O(N) time, in the above sequence, flag[0] will be accessed once (after it's set, it will never be looked again), flag[1] is also accessed once for the same reason; however, flag[2] will be accessed twice (the first time it is reached from Seq[0], it will be set; the second time it is reached from Seq[1], it will be checked once), flag[3] three times (set when reached from Seq[0], then checked twice when reached from Seq[1] and Seq[2])... In the end, flag will be accessed 1+2+3+...+N ~ O(N^2) times. Hence, the amortized time of your solution is O(N^2).

    There is a very simple greedy approach (although I personally understand it as an extremely simplified form of BFS) which you may find in other discussion threads under this question and/or Jump Game II.


  • 0
    V

    Thanks for your help. At first I think it as a O(N) time method because I only considered the O(N) write times of flag array, but I ignore the O(N^2) read times of flag array, which cost most time in my method. Your answer makes me clear about this problem.


Log in to reply
 

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