Given an integer array height[] where height[i] represents the height of the i-th stair, a frog starts from the first stair and wants to reach the top. From any stair i, the frog has two options: it can either jump to the (i+1)th stair or the (i+2)th stair. The cost of a jump is the absolute difference in height between the two stairs. Determine the minimum total cost required for the frog to reach the top.
Here’s the [Problem Link] to begin with.
Example:
Input: heights[] = [20, 30, 40, 20]
Output: 20
Explanation: Minimum cost is incurred when the frog jumps from stair 0 to 1 then 1 to 3:
jump from stair 0 to 1: cost = |30 - 20| = 10
jump from stair 1 to 3: cost = |20-30| = 10
Total Cost = 10 + 10 = 20
Input: heights[] = [30, 20, 50, 10, 40]
Output: 30
Explanation: Minimum cost will be incurred when frog jumps from stair 0 to 2 then 2 to 4:
jump from stair 0 to 2: cost = |50 - 30| = 20
jump from stair 2 to 4: cost = |40-50| = 10
Total Cost = 20 + 10 = 30
Constraints:
- 1 <= height.size() <= 105
- 0 <= height[i]<=104
Recursive Approach (Brute Force)
Intuition and Approach
The intuitive way to solve this is to think recursively: at any step index, the frog could have come from either the previous step (index-1) or the one before that (index-2), paying the respective jump costs. To find the minimum cost to reach index, we calculate the cost from both possible previous positions and choose the minimum.
Why does this work? It’s like exploring a tree of decisions where each node represents a step, and branches represent jump choices (1 or 2 steps). We start from the end and work backwards recursively, ensuring we cover all paths but pick the cheapest one. However, this leads to overlapping subproblems (e.g., computing cost to reach step 3 multiple times), causing exponential time, hence, it’s brute force. For students: Imagine the frog “asking” recursively, “What’s the best way to get here from below?” and summing up the answers with jump costs. This builds the solution from base case (step 0, cost 0) upwards.
Code Implementation
class Solution:
def func(self, height, index):
if index == 0:
return 0
jump1 = self.func(height, index - 1) + abs(height[index] - height[index - 1])
if index > 1:
jump2 = self.func(height, index - 2) + abs(
height[index] - height[index - 2]
)
else:
jump2 = float("inf")
return min(jump1, jump2)
def minCost(self, height):
n = len(height)
return self.func(height, n - 1)Code Explanation
The code defines a recursive function func that computes the min cost to reach a given index from step 0. It checks the base case (if at index 0, cost is 0). Otherwise, it recursively calculates the cost of jumping from index-1 (always possible) and from index-2 (if index > 1), adds the absolute height difference for each, and returns the minimum of these options. The main minCost function calls this for the last index. This mirrors the decision tree, exploring all paths without storing results, which is why it’s inefficient for large n.
Time and Space Complexity
- Precise: Time complexity is O(2^n) because each call branches into up to 2 subcalls, leading to an exponential number of operations in the worst case. Space complexity is O(n) due to the recursion stack (maximum depth n).
- Simplified: Time is exponential (like O(2^n)), which is too slow for large n (e.g., n=100 would take forever). Space is linear O(n), mainly from the call stack—think of it as storing n levels of function calls.
Conclusion
The recursive approach is great for understanding the problem’s decision-making nature but inefficient due to redundant calculations. It’s a starting point for optimization, next, we’ll add memoization to fix the overlaps!
Memoization Approach (Top-Down DP)
Intuition and Approach
Building on the recursive idea, we notice many subproblems are recomputed (e.g., cost to reach step 5 is calculated multiple times from different paths). To optimize, we use memoization: a DP array to store results of subproblems. When we compute the cost for an index, we check if it’s already stored; if yes, return it; else, compute, store, and return.
Why does this work? It turns the exponential tree into a linear computation by caching results, avoiding recomputation. For students: Imagine the frog now has a “notebook” (DP array) where it writes down the min cost to each step after calculating once. This top-down approach starts from the end, fills the notebook as needed, and ensures each step is computed only once. It’s dynamic programming because we break the problem into subproblems and store solutions.
Code Implementation
class Solution:
def func(self, height, index, dp):
if index == 0:
return 0
if dp[index] != -1:
return dp[index]
jump1 = self.func(height, index - 1, dp) + abs(
height[index] - height[index - 1]
)
if index > 1:
jump2 = self.func(height, index - 2, dp) + abs(
height[index] - height[index - 2]
)
else:
jump2 = float("inf")
dp[index] = min(jump1, jump2)
return dp[index]
def minCost(self, height):
n = len(height)
dp = [-1] * n
return self.func(height, n - 1, dp)Code Explanation
This extends the recursive code by adding a DP array initialized to -1. In func, before recursing, it checks if the result for the current index is already in DP; if so, it uses it. After computing the min of jump1 and jump2, it stores the result in DP[index]. This way, the recursion still explores from the top but memoizes results, ensuring each index is processed only once. The main function sets up the DP array and calls func for the end.
Time and Space Complexity
- Precise: Time complexity is O(n) because each index is computed exactly once (memoization avoids repeats). Space complexity is O(n) for the DP array + O(n) for the recursion stack.
- Simplified: Time is linear O(n), perfect for n up to 10^5. Space is O(n + n) which simplifies to O(n)—think of it as O(n) storage plus temporary stack space.
Conclusion
Memoization transforms the brute force into an efficient solution by caching, making it practical. However, the recursion stack can cause issues for very large n—let’s move to bottom-up tabulation to eliminate that!
Tabulation Approach (Bottom-Up DP)
Intuition and Approach
Instead of recursing from the top, we build the solution from the bottom up: start from step 0 (cost 0) and iteratively compute the min cost for each subsequent step using a DP array. For each index, calculate the cost from index-1 and index-2 (if possible), and store the minimum.
Why does this work? It avoids recursion entirely, filling the DP table in order, ensuring dependencies are resolved (e.g., dp uses dp and dp, which are already computed). For students: Picture filling a table row by row, like climbing the stairs yourself— at each step, you look back 1 or 2 steps, add the jump cost, and note the cheapest way. This eliminates stack overflow and is straightforward for iteration lovers.
Code Implementation
class Solution:
def minCost(self, height):
n = len(height)
dp = [-1] * n
dp[0] = 0
for index in range(1, n):
jump1 = dp[index - 1] + abs(height[index] - height[index - 1])
if index > 1:
jump2 = dp[index - 2] + abs(height[index] - height[index - 2])
else:
jump2 = float("inf")
dp[index] = min(jump1, jump2)
return dp[n - 1]Code Explanation
We initialize a DP array with dp = 0. Then, loop from index 1 to n-1: for each, compute jump1 (from previous) and jump2 (from two back, if possible), take the min, and store in dp[index]. Finally, return dp[n-1]. This builds the min costs progressively, using previously computed values, without any recursion.
Time and Space Complexity
- Precise: Time complexity is O(n) due to a single loop iterating n times, each with constant operations. Space complexity is O(n) for the DP array.
- Simplified: Time is O(n), same as memoization but without recursion overhead. Space is O(n)—just the array size, easy to understand as storing one value per step.
Conclusion
Tabulation is reliable and stack-free, but we can optimize space further since we only need the last two values at any point, enter space optimization!
Tabulation (Space Optimization) Approach (Optimal)
Intuition and Approach
Observing that in tabulation, we only use dp[index-1] and dp[index-2] to compute dp[index], we don’t need the full array. Instead, use two variables (prev and prev2) to track the last two costs, updating them as we go.
Why does this work? It maintains the bottom-up order but minimizes space to constants. For students: It’s like climbing with a short memory, you only remember the cost to the last two steps, update for the current, and shift the memories forward. This is the optimal way, achieving O(n) time with O(1) space, ideal for constraints where space matters.
Code Implementation
class Solution:
def minCost(self, height):
n = len(height)
prev2 = 0
prev = 0
for index in range(1, n):
jump1 = prev + abs(height[index] - height[index - 1])
if index > 1:
jump2 = prev2 + abs(height[index] - height[index - 2])
else:
jump2 = float("inf")
curr = min(jump1, jump2)
prev2 = prev
prev = curr
return prevCode Explanation
Initialize prev2 and prev to 0 (costs for index 0 and effectively index -1). Loop from 1 to n-1: compute jump1 using prev, jump2 using prev2 (if available), take min as curr. Then shift: prev2 becomes prev, prev becomes curr. At the end, prev holds the min cost for n-1. This simulates the DP array but with just variables, updating in place.
Time and Space Complexity
- Precise: Time complexity is O(n) from the loop. Space complexity is O(1) since only a few variables are used, independent of n.
- Simplified: Time is O(n), efficient as before. Space is constant O(1)—no array needed, just a handful of variables, making it super lightweight.
Conclusion
Space-optimized tabulation is the pinnacle: fast, memory-efficient, and elegant. Use this in interviews to show optimization skills!
Overall Conclusion
Mastering the Frog Jump problem from GeeksforGeeks teaches core DP concepts, from naive recursion to optimized solutions. Start with recursion for intuition, then optimize with memoization or tabulation, and finish with space efficiency. Practice on similar problems like “Min Cost Climbing Stairs” on LeetCode.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
