Easy to understand greedy O(n) algorithm


  • 0
    N

    Idea:
    start from the next node where last step ends to the node where the last step can reach, remember the farthest index this step can reach. Go until there is no way to go or reach the end
    Example: 2, 3,1,2,1,4
    The first step can reach A[2] becase A[0] is 2, next loop go through from A[1] to A[2], for A[1] it can go to 1 (node index)+3(node value) =4, for A[2], it go reach 2 (node index)+1(node value) = 3, the max inde step 2 can reach is 4 then. The next step goes from A[3] to A[4], get where it can reach for next step, it's 6. It reach the end, we know the min steps. For the case, it can't reach end, the max step it can go small than the start, terminate and return 0.

    Since it goes through the array only once, it's O(n), O(1) solution

        class Solution {
    public:
        int jump(int A[], int n) {
        if(n<=1) return 0;
    
    	int i =1;
    	int minstep = 1;
    	int maxDis = A[0];  //the max index the next step can go
    	while((maxDis+1)>i && (maxDis< (n-1)))  // when maxDis + 1 <=i, it means it can't go further, return 0
    	{
    		int j = maxDis+1; 
    		for(;i<j;i++) // caculate the max distance the next step can go
    			maxDis = max(A[i] + i, maxDis);
    		minstep++;
    	}
    	return (maxDis>=n-1)?minstep:0;
        }
    };

  • 1
    L

    How about below code:

    public class Solution
    {
        public int jump(int[] A)
        {
            if (A.length > 1)
            {
                // step number.
                int step = 1;
                // current position.
                int i = 0;
                // The furthest position we can reach in this jump.
                for (int next = A[0]; next < A.length - 1;)
                {
                    // The furthest position we can reach in next jump.
                    int newNext = next;
                    
                    for (; i <= next; ++i)
                    {
                        newNext = Math.max(newNext, A[i] + i);
                    }
                    // We may be not able to move further any more.
                    if (newNext <= next)
                    {
                        return -1;
                    }
                    
                    next = newNext;
                    ++step;
                }
                return step;
            }
            else
            {
                return 0;
            }
        }
    }

  • 0
    J

    Nice. I've rewritten your code:

    class Solution {
    public:
        int jump(int A[], int n) {
            if (n < 1) return -1;
            if (n == 1) return 0;
            int steps = 1;
            int power = A[0];
            int next = power;
            int newNext = next;
            for (int i = 1; i < n && power-- > 0; i++) {
                if (next >= n - 1) break;
                if (A[i] > power) power = A[i];
                if (i + A[i] > newNext) newNext = i + A[i];
                if (i == next) {
                    steps++;
                    next = newNext;
                }
            }
            return power >= 0 ? steps : -1;
        }
    };
    

Log in to reply
 

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