Jump Game

Problem

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

Return true if you can reach the last index starting from index 0, or false otherwise.

Examples

Example 1:

Input: nums = [1,2,0,1,0]

Output: true

Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.

Example 2:

Input: nums = [1,2,1,0,1]

Output: false

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

You should aim for a solution with O(n) time and O(1) space, where n is the size of input array.

Solution

The DFS branches over all possible jumps, but the only information that matters is the farthest reachable index; since reachable positions form a contiguous interval and farther reach is never worse, the branching state can be collapsed into a greedy frontier.

class Solution {
public:
    bool canJump(const vector<int>& nums) {
        int farthest = 0;
        for (int i = 0; i < nums.size(); ++i) {
            // We are at an index that is over how far we can actually get to
            if (i > farthest) { return false; }
            // From this reachable index, extend how far we can get
            farthest = std::max(farthest, i + nums[i]);
            if (farthest >= nums.size()) {
                return true;
            }
        }
        return true;
    }
};

DFS asks whether we can jump to the end, starting at the current index. This is an O(n^2) solution

class Solution {
public:
    bool canJump(const vector<int>& nums) {
        // Whether we can reach end from index
        std::vector<int> memo(nums.size(), -1);
        std::function<bool(int)> dfs;
        dfs = [&](int idx) -> bool {
            // Ran off the end
            if (idx >= nums.size()) { return false; }
            // Reached the end
            if (idx == nums.size() - 1) { return true; }
            // We've seen this one before
            if (memo[idx] != -1) { return memo[idx]; }
            // iterate over the amount of jumps we can do
            for (int i = 1; i <= nums[idx]; ++i) {
                if (dfs(idx + i)) {
                    memo[idx] = true;
                    return true;
                }
            }
            // None of the jumps reached, false
            memo[idx] = false;
            return false;
        };
        return dfs(0);
    }
};