17ms AC C++ code, very easy to understand


  • 10
    A
    int jump(int A[], int n) {
    		int i = 0, j = 1, cnt = 0, mx;
    
    		if (n == 1) return 0;
    
    		while (i < n - 1 && i + A[i] < n - 1) {
    			for (mx = j; j <= i + A[i]; j++) { mx = (mx + A[mx] <= j + A[j]) ? j : mx; }
    			i = mx; cnt++;
    		}
    		return ++cnt; /* One more step to last index. */
    	}
    

    All we have to do is to iterate though all positions we can jump from where we standing, find the largest i + A[i] (greedy) and jump to that index. O(n) in time and constant space.


  • 0
    S

    Brilliant!

    Just one quick question: I've always wondered, what does AC stand for? accepted?


  • 0
    A

    Yes, you are correct.


Log in to reply
 

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