Simple O(n) greedy solution

  • 0
    class Solution {
        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

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

  • 0

    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.