Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Frog Jump with Variable Steps

MEDIUMProblemSolveExternal Links

Description

A frog is standing at the bottom of a staircase and wants to reach the top. The staircase has n stairs, and each stair has a specific height. The frog starts at stair 0 and wants to reach stair n-1 (the last stair).

At each stair, the frog has two choices:

  • Jump 1 step to the next stair (stair i → stair i+1)
  • Jump 2 steps to skip one stair (stair i → stair i+2)

Every time the frog jumps from stair i to stair j, it pays a cost equal to the absolute difference in heights between those two stairs: |height[j] - height[i]|.

Given an array height[] where height[i] represents the height of the i-th stair, find the minimum total cost the frog needs to pay to reach the last stair from the first stair.

Examples

Example 1

Input: height = [20, 30, 40, 20]

Output: 20

Explanation: The frog can take the following path to minimize cost:

  • Jump from stair 0 (height 20) to stair 1 (height 30): cost = |30 - 20| = 10
  • Jump from stair 1 (height 30) to stair 3 (height 20): cost = |20 - 30| = 10

Total cost = 10 + 10 = 20. The frog skips stair 2 (height 40) to avoid the large height difference. If it had gone 0→1→2→3, the cost would be |30-20| + |40-30| + |20-40| = 10 + 10 + 20 = 40, which is worse.

Example 2

Input: height = [30, 20, 50, 10, 40]

Output: 30

Explanation: The optimal path is:

  • Jump from stair 0 (height 30) to stair 2 (height 50): cost = |50 - 30| = 20
  • Jump from stair 2 (height 50) to stair 4 (height 40): cost = |40 - 50| = 10

Total cost = 20 + 10 = 30. Other paths like 0→1→2→3→4 would cost |20-30| + |50-20| + |10-50| + |40-10| = 10 + 30 + 40 + 30 = 110, which is far worse.

Example 3

Input: height = [10, 10, 10]

Output: 0

Explanation: All stairs have the same height, so every jump costs |10 - 10| = 0 regardless of which path the frog takes. Whether the frog goes 0→1→2 or 0→2, the total cost is 0.

Constraints

  • 1 ≤ height.size() ≤ 10^5
  • 0 ≤ height[i] ≤ 10^4

Editorial

Brute Force

Intuition

The most natural way to think about this problem is to consider it from the frog's perspective standing at the last stair. How did the frog get here? It must have arrived from either the previous stair (one jump back) or two stairs back (two jumps back). Whichever path had a lower total cost is the one we want.

This reasoning applies recursively to every stair. To know the minimum cost to reach stair n, we need to know the minimum cost to reach stair n-1 and stair n-2. To know the cost to reach stair n-1, we need stair n-2 and stair n-3, and so on. This naturally leads to a recursive solution.

Think of it like choosing a route through a series of hills. At each hill, you can take a short hop to the next hill or a long leap over one hill. You want to minimize how much total elevation change you endure. The brute force approach tries every possible combination of hops and leaps and picks the cheapest one.

Step-by-Step Explanation

Let's trace the recursive approach for height = [20, 30, 40, 20]:

Step 1: We want minCost(3) — the minimum cost to reach stair 3. The frog could have arrived from stair 2 (one jump) or stair 1 (two jumps). We need to explore both paths.

Step 2: First, explore the path via stair 2. We need minCost(2) before we can compute this option. Recursively expand.

Step 3: For minCost(2), try arriving from stair 1. We need minCost(1).

Step 4: minCost(1) = |h[1] - h[0]| = |30 - 20| = 10. This is a base case — there is only one way to reach stair 1 (jump from stair 0).

Step 5: Back to minCost(2), also try arriving from stair 0. We need minCost(0).

Step 6: minCost(0) = 0. Base case — the frog is already at stair 0, no cost needed.

Step 7: Now compute minCost(2) = min(minCost(1) + |h[2]-h[1]|, minCost(0) + |h[2]-h[0]|) = min(10 + 10, 0 + 20) = min(20, 20) = 20.

Step 8: Back to minCost(3), now try the other path — arriving from stair 1 directly. We need minCost(1) again.

Step 9: minCost(1) = 10. But we already computed this in Step 4! The recursion has no memory of past results, so it repeats this entire computation. This is wasted work.

Step 10: Finally, minCost(3) = min(minCost(2) + |h[3]-h[2]|, minCost(1) + |h[3]-h[1]|) = min(20 + 20, 10 + 10) = min(40, 20) = 20.

Recursive Exploration of minCost(3) — Watch how the recursion tree expands as we compute minCost(3), revealing duplicate subproblems that cause exponential work.

Algorithm

  1. Define a recursive function minCost(n) that returns the minimum cost to reach stair n
  2. Base cases:
    • minCost(0) = 0 — no cost to stand on the starting stair
    • minCost(1) = |height[1] - height[0]| — only one way to reach stair 1
  3. For any stair n ≥ 2, compute:
    • Option A: come from stair n-1 → minCost(n-1) + |height[n] - height[n-1]|
    • Option B: come from stair n-2 → minCost(n-2) + |height[n] - height[n-2]|
    • Return min(Option A, Option B)
  4. Call minCost(n-1) where n is the total number of stairs

Code

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class Solution {
public:
    int solve(int n, vector<int>& height) {
        // Base case: no cost at the starting stair
        if (n == 0) return 0;
        // Base case: only one jump possible to reach stair 1
        if (n == 1) return abs(height[1] - height[0]);
        
        // Try both options and take the minimum
        int jumpOne = solve(n - 1, height) + abs(height[n] - height[n - 1]);
        int jumpTwo = solve(n - 2, height) + abs(height[n] - height[n - 2]);
        
        return min(jumpOne, jumpTwo);
    }
    
    int minCost(vector<int>& height) {
        int n = height.size();
        return solve(n - 1, height);
    }
};
class Solution:
    def minCost(self, height):
        def solve(n):
            # Base case: no cost at the starting stair
            if n == 0:
                return 0
            # Base case: only one jump to reach stair 1
            if n == 1:
                return abs(height[1] - height[0])
            
            # Try both options and take the minimum
            jump_one = solve(n - 1) + abs(height[n] - height[n - 1])
            jump_two = solve(n - 2) + abs(height[n] - height[n - 2])
            
            return min(jump_one, jump_two)
        
        return solve(len(height) - 1)
class Solution {
    public int minCost(int[] height) {
        return solve(height.length - 1, height);
    }
    
    private int solve(int n, int[] height) {
        // Base case: no cost at the starting stair
        if (n == 0) return 0;
        // Base case: only one jump to reach stair 1
        if (n == 1) return Math.abs(height[1] - height[0]);
        
        // Try both options and take the minimum
        int jumpOne = solve(n - 1, height) + Math.abs(height[n] - height[n - 1]);
        int jumpTwo = solve(n - 2, height) + Math.abs(height[n] - height[n - 2]);
        
        return Math.min(jumpOne, jumpTwo);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each stair, the recursion branches into two calls (one-step and two-step). This creates a binary recursion tree of height n. In the worst case, the number of nodes in this tree is 2^n. For n = 30, that is over 1 billion operations — far too slow.

This is the same recurrence as the Fibonacci sequence: T(n) = T(n-1) + T(n-2), which grows exponentially.

Space Complexity: O(n)

The recursion stack can go at most n levels deep (one call per stair in the longest branch). Each stack frame uses constant space, so the total recursion stack space is O(n).

Why This Approach Is Not Efficient

The recursive approach recomputes the same subproblems over and over. As we saw in the animation, minCost(1) was computed twice for just 4 stairs. For larger inputs, this duplication explodes exponentially.

With n = 10^5 stairs, the recursion would attempt roughly 2^(10^5) operations — a number so large it would take longer than the age of the universe to complete. The problem's constraint of n ≤ 10^5 makes this approach completely impractical.

The root cause is overlapping subproblems: the same stair's minimum cost is needed by multiple parent calls. For example, minCost(k) is needed by both minCost(k+1) and minCost(k+2). Without storing already-computed results, we redo the same work exponentially many times.

Key insight: If we store (memoize) the result of each minCost(i) the first time we compute it, we never need to recompute it. Even better, since we only need results for stairs 0 through n-1 and each depends only on the previous two, we can fill a table from left to right in a single pass.

Line chart comparing exponential O(2^n) recursion growth vs linear O(n) DP growth as n increases
Line chart comparing exponential O(2^n) recursion growth vs linear O(n) DP growth as n increases

Better Approach - Dynamic Programming (Tabulation)

Intuition

Instead of starting from the last stair and recursing backward (top-down), we can flip the approach: start from the first stair and build up (bottom-up).

We create a dp array where dp[i] stores the minimum cost to reach stair i. We know dp[0] = 0 (the frog starts here for free) and dp[1] = |height[1] - height[0]| (only one way to reach stair 1). For every subsequent stair i, we simply check the two options:

  • Come from stair i-1: cost = dp[i-1] + |height[i] - height[i-1]|
  • Come from stair i-2: cost = dp[i-2] + |height[i] - height[i-2]|

We take the minimum. Since we process stairs in order from 0 to n-1, by the time we reach stair i, both dp[i-1] and dp[i-2] are already computed. There is no redundant work.

Think of filling out a table row by row: each cell only looks at the two cells immediately to its left. One pass through the table gives us our answer.

Step-by-Step Explanation

Let's trace with height = [30, 20, 50, 10, 40]:

Step 1: Create a dp array of size 5 to store the minimum cost to reach each stair.

Step 2: dp[0] = 0 — the frog starts at stair 0, so no cost is needed.

Step 3: dp[1] = |h[1] - h[0]| = |20 - 30| = 10 — stair 1 can only be reached from stair 0.

Step 4: For stair 2, consider jumping from stair 1: cost = dp[1] + |h[2] - h[1]| = 10 + |50 - 20| = 10 + 30 = 40.

Step 5: Also consider jumping from stair 0: cost = dp[0] + |h[2] - h[0]| = 0 + |50 - 30| = 0 + 20 = 20. Take the minimum: dp[2] = min(40, 20) = 20.

Step 6: For stair 3, jump from stair 2: cost = dp[2] + |h[3] - h[2]| = 20 + |10 - 50| = 20 + 40 = 60.

Step 7: Jump from stair 1: cost = dp[1] + |h[3] - h[1]| = 10 + |10 - 20| = 10 + 10 = 20. dp[3] = min(60, 20) = 20.

Step 8: For stair 4, jump from stair 3: cost = dp[3] + |h[4] - h[3]| = 20 + |40 - 10| = 20 + 30 = 50.

Step 9: Jump from stair 2: cost = dp[2] + |h[4] - h[2]| = 20 + |40 - 50| = 20 + 10 = 30. dp[4] = min(50, 30) = 30.

Step 10: The frog reaches the last stair with minimum cost dp[4] = 30.

Bottom-Up DP Table Filling for Frog Jump — Watch the dp table being filled left to right. Each cell considers two options (jump from i-1 or i-2) and stores the minimum cost.

Algorithm

  1. Create a dp array of size n where dp[i] = minimum cost to reach stair i
  2. Set base cases:
    • dp[0] = 0 (starting stair)
    • dp[1] = |height[1] - height[0]| (only one option)
  3. For each stair i from 2 to n-1:
    • Compute cost from stair i-1: dp[i-1] + |height[i] - height[i-1]|
    • Compute cost from stair i-2: dp[i-2] + |height[i] - height[i-2]|
    • Store dp[i] = min(cost from i-1, cost from i-2)
  4. Return dp[n-1]

Code

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minCost(vector<int>& height) {
        int n = height.size();
        if (n == 1) return 0;
        
        vector<int> dp(n);
        dp[0] = 0;
        dp[1] = abs(height[1] - height[0]);
        
        for (int i = 2; i < n; i++) {
            int fromPrev = dp[i - 1] + abs(height[i] - height[i - 1]);
            int fromTwoPrev = dp[i - 2] + abs(height[i] - height[i - 2]);
            dp[i] = min(fromPrev, fromTwoPrev);
        }
        
        return dp[n - 1];
    }
};
class Solution:
    def minCost(self, height):
        n = len(height)
        if n == 1:
            return 0
        
        dp = [0] * n
        dp[1] = abs(height[1] - height[0])
        
        for i in range(2, n):
            from_prev = dp[i - 1] + abs(height[i] - height[i - 1])
            from_two_prev = dp[i - 2] + abs(height[i] - height[i - 2])
            dp[i] = min(from_prev, from_two_prev)
        
        return dp[n - 1]
class Solution {
    public int minCost(int[] height) {
        int n = height.length;
        if (n == 1) return 0;
        
        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = Math.abs(height[1] - height[0]);
        
        for (int i = 2; i < n; i++) {
            int fromPrev = dp[i - 1] + Math.abs(height[i] - height[i - 1]);
            int fromTwoPrev = dp[i - 2] + Math.abs(height[i] - height[i - 2]);
            dp[i] = Math.min(fromPrev, fromTwoPrev);
        }
        
        return dp[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array exactly once, from index 2 to n-1. At each index, we perform a constant number of operations (two additions, two absolute values, one comparison). Total: (n-2) iterations × O(1) per iteration = O(n).

Compared to the brute force's O(2^n), this is a dramatic improvement. For n = 10^5, we do about 10^5 operations instead of 2^(10^5) — the difference between a millisecond and eternity.

Space Complexity: O(n)

We allocate a dp array of size n to store the minimum cost for each stair. This grows linearly with input size.

Why This Approach Is Not Efficient

The tabulation approach is excellent in terms of time — O(n) is optimal since we must examine every stair at least once. However, it uses O(n) extra space for the dp array.

With n up to 10^5, this means allocating an array of 100,000 integers. While this is generally acceptable, we can do better.

Look at the recurrence: dp[i] = min(dp[i-1] + ..., dp[i-2] + ...). Computing dp[i] only requires the values at positions i-1 and i-2 — not the entire history of all previous stairs. Once we move past stair i, we never look at dp[0], dp[1], ..., dp[i-3] again.

This means we are wasting memory by storing all n values when only the last two matter at any point. We can replace the entire array with just two variables.

Optimal Approach - Space Optimized DP

Intuition

Since each stair's cost depends only on the costs of the two immediately preceding stairs, we can use a sliding window of size 2 instead of a full array.

We maintain two variables:

  • prev2 — the minimum cost to reach stair i-2
  • prev1 — the minimum cost to reach stair i-1

At each step, we compute the current stair's cost using these two values, then slide the window forward: prev2 becomes the old prev1, and prev1 becomes the newly computed value.

Think of it like a caterpillar moving along the staircase — it only needs to remember the last two positions it touched, not every position it has ever been.

Step-by-Step Explanation

Let's trace with height = [30, 20, 50, 10, 40], using only two variables:

Step 1: Initialize prev2 = 0 (cost to reach stair 0) and prev1 = |h[1]-h[0]| = |20-30| = 10 (cost to reach stair 1).

Step 2: Process stair 2. Jump from stair 1 (prev1): cost = 10 + |h[2]-h[1]| = 10 + |50-20| = 10 + 30 = 40.

Step 3: Jump from stair 0 (prev2): cost = 0 + |h[2]-h[0]| = 0 + |50-30| = 20. curr = min(40, 20) = 20.

Step 4: Slide the window: prev2 ← prev1 = 10, prev1 ← curr = 20.

Step 5: Process stair 3. Jump from stair 2 (prev1): cost = 20 + |h[3]-h[2]| = 20 + |10-50| = 20 + 40 = 60.

Step 6: Jump from stair 1 (prev2): cost = 10 + |h[3]-h[1]| = 10 + |10-20| = 10 + 10 = 20. curr = min(60, 20) = 20.

Step 7: Slide: prev2 ← 20, prev1 ← 20.

Step 8: Process stair 4. Jump from stair 3 (prev1): cost = 20 + |h[4]-h[3]| = 20 + |40-10| = 20 + 30 = 50.

Step 9: Jump from stair 2 (prev2): cost = 20 + |h[4]-h[2]| = 20 + |40-50| = 20 + 10 = 30. curr = min(50, 30) = 30.

Step 10: Slide: prev2 ← 20, prev1 ← 30. Return prev1 = 30.

Space Optimized DP — Sliding Two Variables — Watch how only two variables (prev2 and prev1) slide along the height array, computing each stair's minimum cost without storing the entire dp table.

Algorithm

  1. Handle edge case: if only one stair, return 0
  2. Initialize two variables:
    • prev2 = 0 (cost to reach stair 0)
    • prev1 = |height[1] - height[0]| (cost to reach stair 1)
  3. For each stair i from 2 to n-1:
    • Compute cost from stair i-1: prev1 + |height[i] - height[i-1]|
    • Compute cost from stair i-2: prev2 + |height[i] - height[i-2]|
    • curr = min(cost from i-1, cost from i-2)
    • Slide window: prev2 = prev1, prev1 = curr
  4. Return prev1

Code

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minCost(vector<int>& height) {
        int n = height.size();
        if (n == 1) return 0;
        
        int prev2 = 0;
        int prev1 = abs(height[1] - height[0]);
        
        for (int i = 2; i < n; i++) {
            int curr = min(
                prev1 + abs(height[i] - height[i - 1]),
                prev2 + abs(height[i] - height[i - 2])
            );
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
};
class Solution:
    def minCost(self, height):
        n = len(height)
        if n == 1:
            return 0
        
        prev2 = 0
        prev1 = abs(height[1] - height[0])
        
        for i in range(2, n):
            curr = min(
                prev1 + abs(height[i] - height[i - 1]),
                prev2 + abs(height[i] - height[i - 2])
            )
            prev2 = prev1
            prev1 = curr
        
        return prev1
class Solution {
    public int minCost(int[] height) {
        int n = height.length;
        if (n == 1) return 0;
        
        int prev2 = 0;
        int prev1 = Math.abs(height[1] - height[0]);
        
        for (int i = 2; i < n; i++) {
            int curr = Math.min(
                prev1 + Math.abs(height[i] - height[i - 1]),
                prev2 + Math.abs(height[i] - height[i - 2])
            );
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once from index 2 to n-1, performing a constant number of arithmetic operations at each step. The time complexity is identical to the tabulation approach — O(n).

Space Complexity: O(1)

We use only three integer variables (prev2, prev1, curr) regardless of input size. This is a significant improvement over the O(n) space used by the tabulation approach. For n = 10^5, we save approximately 400 KB of memory (100,000 integers × 4 bytes each).

This is the optimal solution — O(n) time is necessary because we must examine every stair at least once, and O(1) space is the minimum possible since we need at least a few variables to compute the result.