Frog Jump with K Distances: Minimum Energy

95k
0

An array heights stores the height of every stone, and an integer k gives the maximum jump distance.

A frog starts at index 0 and must reach index n - 1. From any index, a jump can be made to any later index within distance k, as long as the destination exists. The energy for one jump equals the absolute difference between both stone heights. Return the minimum total energy required to reach the final stone.

Example 1

Input: heights = [10, 30, 40, 50, 20], k = 3
Output: 30
Explanation: The route 0 -> 1 -> 4 costs |10 - 30| + |30 - 20| = 20 + 10 = 30.

Example 2

Input: heights = [10, 10], k = 5
Output: 0
Explanation: The direct route 0 -> 1 costs |10 - 10| = 0, even though k is larger than the required distance.

Recursion

The final stone can be reached from several earlier stones, not just one or two. The small aha moment is simple: before landing on a stone, the previous position must be one of the last k reachable stones. Each possible previous stone gives a complete route cost.

The same question appears again for every previous stone: minimum energy needed to reach the earlier position. Recursion fits because each choice leads to the same smaller problem. The state solve(index) represents the minimum energy required to reach stone index. The first helper call uses solve(n - 1) because the final stone is the destination and the helper works backward through all valid previous jumps.

For each state, every jump length from 1 to k is tested after confirming a valid previous index. The cheapest complete cost is returned. Direct recursion is easy to understand, but repeated states make the work grow very quickly.

Algorithm

  • Define solve(index) as the minimum energy required to reach stone index, so every recursive call answers the same smaller question.

  • Return 0 at index 0 because the starting stone requires no jump and contributes no energy cost.

  • Start recursion from solve(n - 1) because the final stone represents the complete destination and earlier stones form smaller states.

  • Keep minimumEnergy at infinity before testing jumps so the first valid complete route can safely become the current best.

  • Try every jump length from 1 through k because any reachable stone in the previous allowed window may produce the cheapest route.

  • Add the height difference to solve(previousIndex) only for a non-negative previous index because no stone exists before index 0.

  • Retain the smallest complete route in minimumEnergy and return the value because the cheapest valid predecessor determines the state answer.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Computes the minimum energy required to reach one stone.
int solve(int index, vector<int>& heights, int k) {
// The starting stone needs no jump.
if (index == 0) {
return 0;
}
int minimumEnergy = INT_MAX;
// Every allowed previous stone is tested as the jump source.
for (int jump = 1; jump <= k; jump++) {
int previousIndex = index - jump;
// A jump can be used only when the previous stone exists.
if (previousIndex >= 0) {
int difference = abs(heights[index] - heights[previousIndex]);
// A predecessor answer covers energy to the source.
// The height difference adds the final jump cost.
int jumpEnergy = solve(previousIndex, heights, k) + difference;
minimumEnergy = min(minimumEnergy, jumpEnergy);
}
}
return minimumEnergy;
}
public:
// Returns minimum energy for the final stone.
int frogJump(vector<int>& heights, int k) {
int n = heights.size();
return solve(n - 1, heights, k);
}
};
// Driver code
int main() {
vector<int> heights = {10, 30, 40, 50, 20};
int k = 3;
Solution obj;
cout << obj.frogJump(heights, k) << endl;
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(kN), where N is the maximum recursion depth, because each recursive state can branch into at most k possible previous states.

Space Complexity: O(N), because a sequence of 1-step jumps can create a recursion stack of depth N.

Memoization

Direct recursion keeps asking for the same stone again. For example, several routes into later stones may need the answer for index 1 or index 2. A dp array saves each completed answer, so repeated work disappears.

The state remains solve(index), and dp[index] stores the minimum energy required to reach stone index. Before any state is expanded, the stored value is checked. The recurrence stays unchanged; only a memory layer is added.

Algorithm

  • Create a dp array of size n filled with -1, so every untouched position clearly marks an uncalculated state.

  • Preserve solve(index) as the minimum energy for stone index, because memoization should reuse the recursive meaning without changing the choices.

  • Return 0 at index 0 because the starting stone needs no energy, and reuse dp[index] whenever a stored answer exists to avoid repeated work.

  • Keep minimumEnergy at infinity before exploring predecessors so every valid route can compete for the state answer.

  • Test every non-negative previous index within distance k because each allowed predecessor can lead to a different total energy.

  • Add the jump difference to the memoized predecessor answer and retain the smallest sum because the least costly complete route wins.

  • Store the result in dp[index] before returning and call solve(n - 1) from the public method so future visits reuse each completed state.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Computes and stores the minimum energy for one stone.
int solve(int index, vector<int>& heights, int k, vector<int>& dp) {
// The starting stone needs no jump.
if (index == 0) {
return 0;
}
// A stored answer avoids repeated recursion.
if (dp[index] != -1) {
return dp[index];
}
int minimumEnergy = INT_MAX;
// Every allowed previous stone is tested as the jump source.
for (int jump = 1; jump <= k; jump++) {
int previousIndex = index - jump;
// A jump can be used only when the previous stone exists.
if (previousIndex >= 0) {
int difference = abs(heights[index] - heights[previousIndex]);
// A stored answer covers energy to the source.
// The height difference adds the final jump cost.
int jumpEnergy = solve(previousIndex, heights, k, dp) + difference;
minimumEnergy = min(minimumEnergy, jumpEnergy);
}
}
// The best computed answer is stored for later requests.
dp[index] = minimumEnergy;
return dp[index];
}
public:
// Returns minimum energy for the final stone.
int frogJump(vector<int>& heights, int k) {
int n = heights.size();
vector<int> dp(n, -1);
return solve(n - 1, heights, k, dp);
}
};
// Driver code
int main() {
vector<int> heights = {10, 30, 40, 50, 20};
int k = 3;
Solution obj;
cout << obj.frogJump(heights, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × k), where N is the number of states, because each state checks at most k allowed predecessors once.

Space Complexity: O(N), because the dp array stores N values and the recursion stack can also grow to a depth of N.

Tabulation

Memoization solves states only after recursive demand appears. Tabulation builds the same answers in order from the starting stone to the final stone.

For a current index, all valid previous indices are smaller, so earlier table values are already available. The recursive call solve(previousIndex) becomes dp[previousIndex]. The same transition becomes an iterative loop over jump lengths.

Algorithm

  • Create a dp array of size n so dp[index] stores the minimum energy for stone index and mirrors the recursive state.

  • Set dp[0] to 0 because the starting stone needs no jump and supplies the base answer for later states.

  • Process indices from 1 through n - 1 so every allowed predecessor has a completed table value before use.

  • Keep minimumEnergy at infinity for each current index so the first valid predecessor can establish a safe initial answer.

  • Examine jump lengths from 1 through k and skip negative previous indices because only existing stones can start a jump.

  • Add each height difference to dp[previousIndex] and keep the smallest sum because every table state needs the cheapest complete route.

  • Store the selected value in dp[index] and return dp[n - 1] because the final table position represents the full journey.

Dry Run

Frog Jump with k Distances Tabulation

Frog Jump with k Distances Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns minimum energy with bottom-up DP.
int frogJump(vector<int>& heights, int k) {
int n = heights.size();
vector<int> dp(n, 0);
// Earlier DP states are prepared before every current state.
for (int index = 1; index < n; index++) {
int minimumEnergy = INT_MAX;
// Every allowed previous stone is tested as the jump source.
for (int jump = 1; jump <= k; jump++) {
int previousIndex = index - jump;
// A jump can be used only when the previous stone exists.
if (previousIndex >= 0) {
int difference = abs(heights[index] - heights[previousIndex]);
// A table value covers energy to the source.
// The height difference adds the final jump cost.
int jumpEnergy = dp[previousIndex] + difference;
minimumEnergy = min(minimumEnergy, jumpEnergy);
}
}
dp[index] = minimumEnergy;
}
return dp[n - 1];
}
};
// Driver code
int main() {
vector<int> heights = {10, 30, 40, 50, 20};
int k = 3;
Solution obj;
cout << obj.frogJump(heights, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × k), where N is the number of stones, because each stone checks at most k possible jump lengths.

Space Complexity: O(N), because the dp array stores one value for each of the N stones, while the iterative approach uses no recursion stack.

Space Optimization

The tabulation transition for an index reads only the previous k DP values. Older values are never needed again, because a jump longer than k is not allowed. So the full DP array can be replaced with a circular buffer of size k + 1.

The buffer position index % windowSize stores the answer for the current index. While calculating current, every previous index within distance k reads the stored answer from previousIndex % windowSize. After current is calculated, the same buffer slot is overwritten for the current index. The overwrite is safe because the value from index - windowSize is already outside the allowed jump window.

The variable current still means the minimum energy required to reach the present stone. The shift order is handled by the modulo write: all previous values are read first, then current is written into the circular slot for the current index.

Algorithm

  • Choose windowSize = k + 1 so the current circular slot cannot overwrite any of the previous k answers before all required reads finish.

  • Create a dp window of length windowSize and set dp[0] to 0 because the starting stone needs a stored base answer.

  • Process indices from 1 through n - 1 so every allowed predecessor remains available in the circular window.

  • Keep current at infinity before checking predecessors so the first valid route can safely become the best route.

  • Test every non-negative previous index within distance k because the transition still considers the same allowed jumps as tabulation.

  • Read each predecessor through previousIndex % windowSize so the recent table state maps to the correct circular slot.

  • Compare every predecessor cost and retain the smallest sum in current because the state still represents minimum energy.

  • Write current into index % windowSize only after all reads finish, then return the final circular slot because older states are no longer needed.

Dry Run

Frog Jump with k Distances Space Optimization

Frog Jump with k Distances Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum energy using a circular DP window.
int frogJump(vector<int>& heights, int k) {
int n = heights.size();
int windowSize = k + 1;
vector<int> dp(windowSize, 0);
// Keeps only recent reachable DP answers.
for (int index = 1; index < n; index++) {
int current = INT_MAX;
// Read every allowed predecessor before a write.
// Early writes could erase a required DP value.
for (int jump = 1; jump <= k; jump++) {
int previousIndex = index - jump;
// A jump can be used only when the previous stone exists.
if (previousIndex >= 0) {
int previousSlot = previousIndex % windowSize;
int difference = abs(heights[index] - heights[previousIndex]);
// Compare each complete predecessor cost.
// Keep the cheapest cost for the current stone.
int jumpEnergy = dp[previousSlot] + difference;
current = min(current, jumpEnergy);
}
}
// Write current after all predecessor reads.
// The modulo shift advances the DP window.
int currentSlot = index % windowSize;
dp[currentSlot] = current;
}
return dp[(n - 1) % windowSize];
}
};
// Driver code
int main() {
vector<int> heights = {10, 30, 40, 50, 20};
int k = 3;
Solution obj;
cout << obj.frogJump(heights, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × k), where N is the number of stones, because each stone checks at most k previous stones.

Space Complexity: O(k), because the circular dp array stores only the most recent k + 1 states, which simplifies to O(k).

Interview follow-up Questions

Yes. A jump still needs an existing destination. When k is larger than the remaining distance, only available later stones are considered.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

Input: prices = [1, 3, 2, 8, 4, 9] , fee = 2 Output: 8 Explanation: Buying at 1 and selling at 8 earns 8 - 1 - 2 = 5 . Buying at 4 and selling at 9 earns 9 - 4 - 2 = 3 . The maximum total profit is...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0