Coding

Frog Jump

Asked at

Amazon

Apple

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

A frog wants to climb a staircase with **n **steps. Given an integer array heights, where heights[i] contains the height of the i****th step.

To jump from the** ith** step to the** jth**** **step, the frog requires abs(heights[i] - heights[j]) energy, where abs() denotes the absolute difference. The frog can jump from any step either **one **or **two **steps, provided it exists.

Return the minimum amount of energy required by the frog to go from the** 0****th** step to the **(n-1)**th step.

Input: heights = [2, 1, 3, 5, 4] Output: 2 Explanation: One possible route can be, 0th step -> 2nd Step = abs(2 - 3) = 1 2nd step -> 4th step = abs(3 - 4) = 1 Total = 1 + 1 = 2.

Input: heights = [7, 5, 1, 2, 6] Output: 9 Explanation: One possible route can be, 0th step -> 1st Step = abs(7 - 5) = 2 1st step -> 3rd step = abs(5 - 2) = 3 3rd step -> 4th step = abs(2 - 6) = 4 Total = 2 + 3 + 4 = 9.

Input: nums = [3, 10, 3, 11, 3]

1 <= n <= 104
0 <= heights[i] <= 104

cpp

class Solution {
public:
    int frogJump(vector<int>& heights) {

    }
};

java

class Solution {
    public int frogJump(int[] heights) {
        
    }
}

python

class Solution:
    def frogJump(self, heights):

javascript

class Solution {
    frogJump(heights) {

    }
}

csharp

public class Solution
{
    public int frogJump(int[] heights)
    {
        
    }
}

func frogJump(heights []int) int {
	
}

Stuck? Show a way to structure it+

01Define dp[i] as the minimum energy needed to reach step i.
02Transition from i - 1 and, when available, i - 2.
03Keep only the previous two values for constant extra space.
04Handle zero or one step before applying the general recurrence.

Reference answer

Let dp[i] be the minimum energy required to reach step i. The last jump comes either from i - 1 or i - 2, so dp[i] = min(dp[i-1] + abs(height[i] - height[i-1]), dp[i-2] + abs(height[i] - height[i-2])), omitting the second option when i < 2. Set dp[0] = 0; for one step, no energy is needed. Because each state depends only on the previous two, store them as prev1 and prev2 rather than allocating the full array. Time is O(n) and extra space is O(1). A greedy choice of the cheaper immediate jump is not safe because it ignores the position and height from which later jumps will begin. The DP is correct by considering every possible final jump into each step.

Then expect these follow-ups

What changes if the frog can jump up to k steps?
Tests: transition generalization
How would you reconstruct the chosen sequence of steps?
Tests: path reconstruction

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question