Algorithms to Compute the Minimal Number of Hops

Given an integer list nums where each number represents the maximum number of hops you can make, return the minimum number of hops it would take to reach the last index starting at index 0. You can assume that you can always reach the last index.

Constraints
n ≤ 100,000 where n is the length of nums

Example 1
Input
nums = [3, 3, 2, 0, 1]
Output
2
Explanation
We can jump from index 0 to 1 and then jump straight to the last index by jumping 3 steps.

We are going to use the Dynamic Programming (DP) algorithm and the Greedy Algorithm (Optimal) to compute the number of the hops.

Dynamic Programming Algorithm to Compute the Number of Hops

The Dynamic Programming (DP) formula is (f[i] is the number of hops required to hop to index i):

i ranges from 0 to n (exclusive) and j ranges from i+1 to nums[i]+i.

1
2
3
4
5
6
7
8
9
10
11

int numberOfHops(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> dp(nums.size(), INT_MAX);
    dp[0] = 0;
    for (int i = 0; i < nums.size(); ++ i) {
        for (int j = i + 1; j <= min((int)nums.size() - 1, i + nums[i]); ++ j) {
            dp[j] = min(dp[j], dp[i] + 1);
        }
    }
    return dp.back();
}

int numberOfHops(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> dp(nums.size(), INT_MAX);
    dp[0] = 0;
    for (int i = 0; i < nums.size(); ++ i) {
        for (int j = i + 1; j <= min((int)nums.size() - 1, i + nums[i]); ++ j) {
            dp[j] = min(dp[j], dp[i] + 1);
        }
    }
    return dp.back();
}

The time complexity is O(N^2). The space complexity is O(N).

Greedy Algorithm to Compute the Minimal Number of Hops

We can use Greedy strategy. We use a variable to keep tracking the furthest distance we can hop to, and the number of the hops. If we are at the furthest, we need to hop one more.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int numberOfHops(vector<int>& nums) {
    if (nums.empty()) return 0;
    int best = 0;
    int hops = 0;
    int cur = 0;
    for (int i = 0; i + 1 < nums.size(); ++ i) {
        best = max(best, nums[i] + i);
        if (cur == i) {
            cur = best;
            hops ++;
        }
    }
    return hops;
}

int numberOfHops(vector<int>& nums) {
    if (nums.empty()) return 0;
    int best = 0;
    int hops = 0;
    int cur = 0;
    for (int i = 0; i + 1 < nums.size(); ++ i) {
        best = max(best, nums[i] + i);
        if (cur == i) {
            cur = best;
            hops ++;
        }
    }
    return hops;
}

The time complexity is O(N). The space complexity is O(1) constant.

See also: The Jumping Kangaroo Problem (Dynamic Programming + Greedy Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —