Another way of looking at the problem


  • 8
    G

    0 is like a trap.
    Anytime you fall-in 0, you can't jump no more (except the last one which you are already at target).

    So first, find those traps from start. After we find one, we have to go back to test if this trap is leap-able. This is not efficient.

    If we search from back, whenever a trap is found, we can conveniently convert searching for trap problem to searching for leap-able problem. No need to go back. So one scan, O(n).

    partial code:

    	for(int i = A.length - 2; i >= 0; i--)
    	{
    		if(A[i] == 0)
    		{
    			//start search
    			int zeroIndex = i;
    			for(i = i - 1; i >=0; i--)  //keep using same i to continue searching!
    			{
    				if(A[i] > zeroIndex - i)   //we can overcome this trap!
    				{
    					break;
    				}
    			}
    			if(i == -1) //searched to end and no possible leap
    				return false;
    		}
    	}
    	return true;

  • 0
    L

    Thank you garysui for sharing the idea. I used your idea and got AC.


  • 0
    L

    Thank you garysui for sharing the idea. |
    Very Cool Idea


  • 0
    S

Log in to reply
 

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