Jump Game II (Leet Code)

Problem: https://leetcode.com/problems/jump-game-ii/

Let \(l(i)\) denotes the maximum index I can reach by jumping \(i\) times. Then this problem can be solved by iteratively computing \(l(i)\) until \(i\) exceeds the length of a given array.

int jump(vector<int>& nums) {
    int num_of_jumps = 0;
    int curr = 0;
    int next = nums[0];

    while (curr < nums.size() - 1) {
        int temp = curr;
        for (int i = curr + 1; i <= min(next, (int)nums.size()-1); ++i) {
            temp = max(temp, i + nums[i]);
        }
        curr = next;
        next = temp;
        ++num_of_jumps;
    }

    return num_of_jumps;
}

For \(i\)th iteration, we store \(l(i)\) in curr and \(l(i+1)\) in next. Computing the value of curr is simple; we just take the value of next from the previous iteration. Also, the value of next can be obtained by finding the maximum value of nums[j] where j varies from \(l(i) + 1\) to \(l(i+1)\).

The time complexity is \(O(n)\) where \(n\) is the size of a given array.