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.
1#include <vector>
2#include <iostream>
3using namespace std;
4
5int jump(vector<int>& nums) {
6 int jumps = 0, currentEnd = 0, farthest = 0;
7 for (int i = 0; i < nums.size() - 1; ++i) {
8 farthest = max(farthest, i + nums[i]);
9 if (i == currentEnd) {
10 jumps++;
11 currentEnd = farthest;
12 }
13 }
14 return jumps;
15}
16
17int main() {
18 vector<int> nums = {2, 3, 1, 1, 4};
19 cout << "Minimum jumps: " << jump(nums) << endl;
20 return 0;
21}The algorithm keeps track of the maximum distance that can be reached `farthest` and increments the jump count when reaching the current jump's end. Update the end to the farthest position reached so far.
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.
1using System;
public class Solution {
public int Jump(int[] nums) {
int[] dp = new int[nums.Length];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
for (int i = 1; i < nums.Length; i++) {
for (int j = 0; j < i; j++) {
if (j + nums[j] >= i) {
dp[i] = Math.Min(dp[i], dp[j] + 1);
}
}
}
return dp[nums.Length - 1];
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {2, 3, 1, 1, 4};
Console.WriteLine("Minimum jumps: " + sol.Jump(nums));
}
}This solution initializes a DP array and iterates over possible index combinations to cover the minimum jumps required. Evaluate potential reach and update dp accordingly.