Share a recursive solution


  • 0
    H

    I don't see this solution posted before. Another perspective.

    class Solution {
    public:
        bool canJump(vector<int>& nums) {
            return canJump(nums, nums.size() - 1);
        }
        
        bool canJump(vector<int>& nums, int p) {
            if (!p) return true;
            int d = 1;  // distance to position p
            while (p - d >= 0 && nums[p - d] < d) ++d;
            if (p - d < 0) return false;
            return canJump(nums, p - 1);
        }
    };

  • 0
    T

    Hmm, I came to the same conclusion, but you can make it iterative, which is O(1) space instead of the recursive O(n) space.


Log in to reply
 

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