Frog Jump: Minimum Energy
Reported by candidates from Mygate's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Mygate reportedly put a frog jump problem in front of candidates in January 2025, and the input size is the whole story. With up to 10^5 stones, trying every path of 1-step and 2-step jumps blows up exponentially, so brute force dies fast. This is a classic dynamic programming problem wearing a small costume. You need the minimum energy to reach the last stone, and each stone only depends on the two before it. If you've seen it, it's five lines. If you haven't, it's easy to overthink. StealthCoder is there as a safety net if your mind goes blank during the live OA.
The problem
A frog starts on the first stone of a nonempty array heights. From stone i, it may jump forward to i + 1 or i + 2, provided that stone exists. A jump from stone i to stone j costs abs(heights[i] - heights[j]) units of energy. Return the minimum total energy needed to reach the last stone. The frog pays no energy before its first jump. For a single stone, return 0. Function frogJump(heights: int[]) → long Examples Example 1 heights = [10,20,30,10] return = 20 Jump through stones 0, 1, 3: costs 10 + 10 = 20. Example 2 heights = [10,30,40,20] return = 30 Jump through stones 0, 1, 3: costs 20 + 10 = 30. Example 3 heights = [7] return = 0 The frog already occupies the last stone. Constraints 1 <= heights.length <= 10^5 -10^9 <= heights[i] <= 10^9 Use signed 64-bit arithmetic for total energy and height differences.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Define dp[i] as the minimum energy to reach stone i. Then dp[0] = 0, and dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2])) for i >= 2. For i = 1 there's only one option, the jump from stone 0. The answer is dp[n-1]. You only need the last two values, so space drops to O(1) and time is O(n). The pitfalls are real. Heights go up to 10^9 in magnitude, so differences can hit 2*10^9 and overflow a 32-bit int. Use 64-bit for differences and totals. Also handle n = 1 and n = 2 before touching i-2. Don't reach for greedy, since picking the cheaper next jump can lose on the following one. If you freeze on the recurrence during the live OA, StealthCoder can hand you the solution while you keep your composure.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Frog Jump: Minimum Energy cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Mygate's OA.
Mygate reuses patterns across OAs. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Frog Jump: Minimum Energy FAQ
What's the trick to the Mygate frog jump problem?+
Treat it as DP over stones. The cost to reach stone i is the cheaper of coming from i-1 or i-2, each plus the absolute height difference. Keep only the last two values and you get O(n) time and O(1) space.
Why doesn't greedy work here?+
Taking the cheaper immediate jump ignores what it sets up next. A small step now can land you on a stone where every later jump is expensive. DP compares complete costs to each stone, so it always finds the true minimum.
What edge cases should I test?+
Test a single stone, which returns 0, and two stones, where only one jump exists. Also test large heights like 10^9 and -10^9 together, since differences reach 2*10^9 and overflow 32-bit integers. Use a 64-bit type for the running totals.
Will recursion work for 10^5 stones?+
Plain recursion without memoization is exponential and will time out. Memoized recursion is correct but can hit stack depth limits at 10^5. An iterative loop with two rolling variables is safer and simpler.
How do I prepare for this in 48 hours?+
Write the dp recurrence from memory a few times, then code the rolling-variable version. Practice the closely related climbing stairs and min cost climbing stairs patterns. If you can explain why only two previous states matter, you're ready for this one.