DSA interview question

Frog Jump

Medium · Algorithms · Topics: dynamic programming, recursion

The problem

You're building the core mechanic for a stone-hopping platformer game. A frog starts on the first stone of n stones lined up in a row and must reach the last stone. From any stone i, the frog can jump to either stone i+1 or stone i+2 (skipping one stone). Each jump costs energy equal to the absolute difference in height between the stone jumped from and the stone landed on. Your task: find the minimum total energy required for the frog to reach the last stone.

Example: heights [30, 10, 60, 10, 60, 50] → minimum energy path costs 40 total.

Function signature

int frogJump(int n, vector<int>& heights);

Test cases

Input `heights`	Output	Explanation
`[30,10,60,10,60,50]`	40	Path: 0→1→3→5 → \|30-10\|+\|10-10\|+\|10-50\| = 20+0+40 = 60? verify with code
`[10,20,30,10]`	20	Path likely 0→2→3 or similar, verify with code
`[10]`	0	Single stone, no jump needed
`[10,10]`	0	Two equal-height stones, one jump, cost 0
`[1,100]`	99	Two stones, forced jump, cost = \|1-100\|
`[7,4,4,2,9]`	7	Classic example, minimum energy path

(Confirm: frog starts at stone 0, must reach stone n-1; jumps of exactly 1 or 2 steps only, never backward.)

How interviewers phrase it

"A frog is on stone 0 and wants to reach stone n-1. From stone i, it can jump to i+1 or i+2. Cost of a jump is the absolute height difference. Minimize total cost."
This is a very standard intro-to-DP problem, often used right after Fibonacci/Climbing Stairs to introduce the idea of "cost" associated with transitions, not just counting ways.
Frequently followed immediately by the K-distance variant as a live extension.

Clarifying questions to ask

Can the frog jump only 1 or 2 steps, never more, never backward? Confirm this precisely.
Must the frog land exactly on the last stone (index n-1), not skip past it?
Are heights guaranteed non-negative? Could there be duplicate heights (zero-cost jumps)?
Is n guaranteed to be at least 1? What should happen for n=1 (frog is already at the destination — cost 0)?
Do you want just the minimum energy, or also the actual path of stones visited?

Follow-ups to expect

"What if the frog can jump up to K steps instead of just 1 or 2?"
"Can you solve this with O(1) extra space?"
"Can you solve it recursively with memoization instead of iterative DP?"
"Can you reconstruct the actual sequence of stones visited?"
"What if backward jumps were allowed?"
"How does this compare to Climbing Stairs?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview