Game Theory in Competitive Programming Part 6

Part 6 of Game Theory in CP : Jump Game 2 (Leetcode)

Source

Welcome to part 6 of this series, in case you have missed part 5, here is the link: Part 5

Today we would be discussing the problem : Jump Game II

Problem Statement:

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position, which means from ith position you can jump any number of positions from 1 till nums[i] towards right.

Your goal is to reach the last index in the minimum number of jumps.

The assumption is that you can always reach the last index.

Examples:

Input: nums = [2,3,1,1,4]

Output: 2

Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

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

Output: 2

Constraints:

• 1 <= nums.length <= 3 * 10⁴
• 0 <= nums[i] <= 10⁵

Copyright @ LeetCode — The World’s Leading Online Programming Learning Platform

Hint:

Think greedily, in terms of the farthest you can jump from each position.

Solution:

At every step, consider a range of positions [start, end] and assess the farthest you can reach from that (far). The next range would then be [end+1, far]. This would count as one step since you are taking a jump from the original range to reach wherever you want in the next range. Continue till the end position is inclusive in the range and then return the number of steps taken.

At every step we are taking the greedy approach and using the principal of Optimality, we can guarantee the answer to be correct.

far : max( i + nums[i] ) where start <= i <= end

Initially : start = end = 0, that is we start at the first position.

The next range starts from end + 1 because we have already considered all positions <= end beforehand and don’t need to include them in the next range again.

Source Code:

int jump(vector<int>& nums) {
    int steps = 0, en = 0, far = 0;
    for(int i = 0; i < nums.size()-1; i++) {
        far = i+nums[i] > far ? i+nums[i] : far;
        if(far >= nums.size()-1) { //stopping condition
            steps++;
            break;
        }
        if(i == en) { // the current range has come to an end.
            steps++;
            en = far; //update the end with the next range’s end
        }
    }
    return steps;
}

That’s all for today, stay tuned for further articles in this series.