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

  • 0

    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.