14ms c++ O(n) solution


  • 3
    P
    /*
    Logic: start with last position and backtrack
    Catch : 1. if position i can take you to dest, then reaching position is i is your goal
            2. lets say j<i, and (a[j]+j >= i), then your new dest becomes j 
    */
    class Solution {
    public:
        bool canJump(int a[], int n) {
            int dest = n-1;
            int cur_pos = n-2;
            while(cur_pos >= 0 && dest != 0) {
              if (a[cur_pos] + cur_pos >= dest) {
                  dest = cur_pos;
              }
              cur_pos--;
            }
            return (dest == 0 ? true : false);
        }
    };

  • 0
    W

    @pankit Actually, I do not think the condition dest != 0 in the while loop is necessary. Cause the loop will try every cur_pos. When out of the loop, we can just go and test whether dest == 0(?)


  • 0
    E

    Thank you for your sharing:)
    I think if current position is available, cur_pos can be directly be dest-1.
    if(cur_pos + nums[cur_pos] >= dest){
    dest = cur_pos;
    cur_pos = dest - 1;
    }


Log in to reply
 

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