Sponsored
Sponsored
The greedy approach involves making a jump only when absolutely necessary. Track the maximum index you can reach at each step and make a decision to jump when you get to the maximum of the current window. This ensures the least number of jumps.
Time Complexity: O(n), where n is the number of elements in the array, because we make a single pass through the array.
Space Complexity: O(1), since we are using a fixed amount of extra space.
1function jump(nums) {
2 let jumps = 0, currentEnd = 0, farthest = 0;
3 for (let i = 0; i < nums.length - 1; i++) {
4 farthest = Math.max(farthest, i + nums[i]);
5 if (i === currentEnd) {
6 jumps++;
7 currentEnd = farthest;
8 }
9 }
10 return jumps;
11}
12
13// Test
14let nums = [2, 3, 1, 1, 4];
15console.log("Minimum jumps: " + jump(nums));Calculate the farthest index while iterating, and decide whether to jump when reaching the end of the current range. Adjust the jump range to the farthest calculated reach.
The dynamic programming approach calculates the minimum jumps required to reach each index. For each index, calculate the minimum number of jumps required from all previous indices that can reach the current index. However, this approach is less efficient in terms of time complexity.
Time Complexity: O(n^2), where n is the number of elements.
Space Complexity: O(n), due to the use of a DP array.
1#include <vector>
#include <limits.h>
using namespace std;
int jump(vector<int>& nums) {
vector<int> dp(nums.size(), INT_MAX);
dp[0] = 0;
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (j + nums[j] >= i) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[nums.size() - 1];
}
int main() {
vector<int> nums = {2, 3, 1, 1, 4};
cout << "Minimum jumps: " << jump(nums) << endl;
return 0;
}Use a dynamic table `dp` where `dp[i]` is the fewest number of jumps required to reach index `i`. Iterate over each index and possible previous jumps to determine the smallest number of jumps.