DSA interview question

Frog Jump with K Distances

Medium · Algorithms · Topics: dynamic programming, recursion

The problem

You're building a physics puzzle game where a frog needs to cross a series of n stepping stones to reach the far bank of a river. Each stone has a certain height, and landing involves an energy cost equal to the absolute difference in height between the stone the frog jumps from and the stone it lands on. Unlike the basic version of this game, this frog is stronger — it can jump forward anywhere from 1 to K stones ahead in a single leap (not just 1 or 2). Your task: given the heights of all stones and the max jump distance K, find the minimum total energy cost for the frog to go from the first stone to the last stone.

Example: heights [10, 30, 40, 50, 20], K = 3 → frog can skip more aggressively than the classic 1-or-2-step version, potentially finding a cheaper path.

Function signature

int frogJumpK(int n, int k, vector<int>& heights);

Test cases

Input `heights`	K	Output	Explanation
`[10,30,40,50,20]`	3	30	10→20 direct... verify: jump 0→4 (
`[10,20,30,10]`	1	20	Forced 1-step jumps only: 10+10... verify with code
`[30,10,60,10,60,50]`	2	40	Classic Frog Jump II example
`[10]`	2	0	Single stone, no jump needed
`[10,10,10,10]`	3	0	All equal heights, any jump path costs 0
`[1,100]`	1	99	Two stones, forced single jump, cost =

(Confirm: K is guaranteed >= 1; frog cannot jump backward; frog must land exactly on the last stone, not skip past it.)

How interviewers phrase it

"A frog is on stone 0 of n stones and wants to reach stone n-1. From any stone i, it can jump to any stone from i+1 to i+K. The cost of a jump is the absolute height difference. Minimize total cost."
This is a direct generalization of Frog Jump (1 or 2 steps), often introduced as: "Now what if the frog could jump up to K steps instead of just 1 or 2?"
Sometimes phrased as "minimum cost climbing stairs with variable step size" — same underlying pattern.

Clarifying questions to ask

Can the frog jump any distance from 1 to K, or only exactly K? Confirm it's a range [1, K].
Must the frog land exactly on the last stone, or can it jump past it (and that's fine as long as it reaches or exceeds it)? (Standard version: must land exactly on the last stone.)
Is the frog restricted to jumping only forward, never backward?
Are heights guaranteed non-negative? Can K be larger than n (meaning the frog could jump directly from stone 0 to the last stone)?
What are the expected constraints on n and K? (Determines whether O(n×K) DP is acceptable, or whether a more advanced structure like a sliding window minimum is needed for very large K.)

Follow-ups to expect

"Can you optimize further if K is very large (e.g., close to n)?"
"How does this generalize the basic Frog Jump (K=2) problem?"
"Can you solve this with O(1) extra space?"
"Can you reconstruct the actual path of stones visited?"
"What if backward jumps were also allowed (with some penalty)?"
"What if each stone also has a jump cooldown or energy limit?"

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