Simple O(n) greedy solution


  • 0
    L
    class Solution {
    public:
        int jump(int A[], int n) {
            vector<int> step(n, 0);
                        
            for(int i = 0, l = 1; i < n; i++)  // l represents the first unexplored step
                while(l < n && l - i <= A[i])  // decide if we can make the jump to l
                    step[l++] = step[i] + 1;   // "the first time we reach position l" is the min # of necessary steps
            
            return step[n-1];
        }
    };

  • 0
    Q

    this is O(n*m) where m is the average step size..


  • 0
    L

    Notice that the statement inside the while loop can run at most n times. Overall order is still O(n).


Log in to reply
 

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