O(n) solution comes from a natural thought in C++


  • 0
    E

    Think it backwards from right to left. If {x1, x2, x3} can all reach the last one, which one will you pick? It doesn't matter since there must be a path to any one of them, if there is a global path from 0 to n-1. So f(0, n-1) is equal to f(0, xi), where f(a, b) means there is a path from a to b.

    So what we need to do is to scan backwards and check if all intermediate stones we select can be reached.

    bool canJump(vector<int>& nums)
    {
       if (nums.size() <= 1) {
          return true;
       }
    
       int destStone = nums.size() - 1;
       // Let's see if we can route our way back to the 1st stone
       for (int i = nums.size() - 2; i >= 0; --i) {
          if (i + nums[i] >= destStone) {
             destStone = i;
          }
       }
       return (destStone == 0);
    }
    

Log in to reply
 

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