Problem

Submissions

Hints & solutions

Discuss

Frog Jump

Easy

0/40

Average time to solve is 30m

Contributed by

726 upvotes

Asked in companies

Problem statement

There is a frog on the '1st' step of an 'N' stairs long staircase. The frog wants to reach the 'Nth' stair. 'HEIGHT[i]' is the height of the '(i+1)th' stair.If Frog jumps from 'ith' to 'jth' stair, the energy lost in the jump is given by absolute value of ( HEIGHT[i-1] - HEIGHT[j-1] ). If the Frog is on 'ith' staircase, he can jump either to '(i+1)th' stair or to '(i+2)th' stair. Your task is to find the minimum total energy used by the frog to reach from '1st' stair to 'Nth' stair.

For Example

If the given ‘HEIGHT’ array is [10,20,30,10], the answer 20 as the frog can jump from 1st stair to 2nd stair (|20-10| = 10 energy lost) and then a jump from 2nd stair to last stair (|10-20| = 10 energy lost). So, the total energy lost is 20.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer,' N’, denoting the number of stairs in the staircase,

The next line contains ‘HEIGHT’ array.

Output Format:

For each test case, return an integer corresponding to the minimum energy lost to reach the last stair.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 100000.
1 <= HEIGHTS[i] <= 1000 .

Time limit: 1 sec

Sample Input 1:

2
4
10 20 30 10
3
10 50 10

Sample Output 1:

20
0

Explanation of sample input 1:

For the first test case,
The frog can jump from 1st stair to 2nd stair (|20-10| = 10 energy lost).
Then a jump from the 2nd stair to the last stair (|10-20| = 10 energy lost).
So, the total energy lost is 20 which is the minimum. 
Hence, the answer is 20.

For the second test case:
The frog can jump from 1st stair to 3rd stair (|10-10| = 0 energy lost).
So, the total energy lost is 0 which is the minimum. 
Hence, the answer is 0.

Sample Input 2:

2
8
7 4 4 2 6 6 3 4 
6
4 8 3 10 4 4

Sample Output 2:

7
2

Hints:

1. Think about all the possibilities at each stair.
2. Using recursion, try to divide the problem into subproblems and calculate the answer for each subproblem only once - store it for reusing in the future.
3. The above can also be done iteratively.

Approaches (3)

Approach 1

Approach 2

Approach 3

Recursion

In this approach, we will define a recursive function REC(i,HEIGHT) that will return the minimum energy needed to reach the last stair from the ith stair.

The base case will be if i is greater than or equal to ‘N’ answer will be 0 as we already reached the final stair.

As we have two choices at each step,REC(i) will be the maximum of energy lost for jumping from ith to (i+1)th step + REC(i+1) and energy lost for jumping from i th to (i+2)th step + REC(i+2).

The final answer will be REC(1, HEIGHTS) corresponding to the minimum energy required to reach the last stair from the first stair.

Algorithm:

Defining 'REC'(i,’ HEIGHTS’) function :
- If i is equal to the length of ‘HEIGHTS’ - 1:
  - Return 0.
- Set ‘ONE_JUMP’ as INF.
- Set ‘TWO_JUMP’ as INF.
- If i+1 < length of ‘HEIGHTS’:
  - Set ‘ONE_JUMP’ as abs(HEIGHTS[i]-HEIGHTS[i+1]) + REC(i+1,HEIGHTS).
- If i+2 < length of ‘HEIGHTS’:
  - Set ‘TWO_JUMP’ as abs(HEIGHTS[i]-HEIGHTS[i+2]) + REC(i+2,HEIGHTS).
- Set ‘ANS’ as minimum of ONE_JUMP and TWO_JUMP.
- Return ‘ANS’.
Set ‘ANS’ as REC(1,HEIGHTS).
Return ‘ANS’.

Time Complexity

O(2^N), where ‘N’ is the number of stairs.

In this approach, in the worst case, we will run the 'REC' function for all possible combinations. Each stair has two choices. So the total number of combinations is 2^N. Hence the overall time complexity is O(2^N).

Space Complexity

O( 2^N), where ‘N’ is the number of stairs.

In this approach, in the worst case, we are making 2^N calls of the 'REC'() function. It will consume stack memory. Hence the overall space complexity is O(2^N).

(75% EXP penalty)

(100% EXP penalty)

Frog Jump

yash Sakhareliya

Interview problems

Easiest C++ Solution using Memoization and tabulization

// dp solution memoization top-down

int f1(int n, vector<int> &heights, vector<int>& dp){

// base case

if(n == 0) return 0;

// for dp memoization if ans is store return ans

if(dp[n] != -1) return dp[n];

// do all possible task that index

int left = f1(n-1,heights, dp) + abs(heights[n]-heights[n-1]);

// the right is not always possible e.g: f(1) declare right = INT_MAX

int right = INT_MAX;

if(n > 1)

right = f1(n-2, heights, dp) + abs(heights[n]-heights[n-2]);

// return the ans according yoyr question

// and store the ans in dp

return dp[n] = min(left, right);

}

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

{

// initialize the vector for dp

// vector<int> dp(n+1,-1);

// return f1(n-1,heights,dp);

// tabulization approch

vector<int> dp(n, -1);

// apporch as per base case

dp[0] = 0;

for(int i=1; i<n; i++){

// find first step

int fs = dp[i-1] + abs(heights[i]-heights[i-1]);

// find ss step

int ss = INT_MAX;

if(i > 1) ss = dp[i-2] + abs(heights[i]-heights[i-2]);

// find cur index value

dp[i] = min(fs, ss);

}

return dp[n-1];

}

181 views

0 replies

0 upvotes

Aryan Kumar

Interview problems

Easiest C++ Solution using Memoization

#include <bits/stdc++.h>

int fn(int ind, vector<int> &heights, vector<int> &dp){

if (ind==0) return 0;

if (dp[ind]!= -1) return dp[ind];

int left= fn(ind-1, heights, dp) + abs(heights[ind]- heights[ind-1]);

int right= INT_MAX;

if (ind>1) right= fn(ind-2, heights, dp) + abs(heights[ind]- heights[ind-2]);

return dp[ind]= min(left, right);

}

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

{

vector<int> dp(n+1, -1);

return fn(n-1, heights, dp);

}

151 views

0 replies

0 upvotes

Bhuwan Saretia

Interview problems

C++ Solution || Most Optimised Approach

#include <bits/stdc++.h>

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

{

n--;

int prev = 0;

int curr = abs(heights[1] - heights[0]);

for(int i=2; i<=n; i++)

{

int ans = min((prev + abs(heights[i-2] - heights[i])), (curr + abs(heights[i-1]-heights[i])));

prev = curr;

curr = ans;

}

return curr;

}

172 views

0 replies

1 upvote

Aman Borkar

Interview problems

Answer in C++ (all methods)

#include <bits/stdc++.h>

//brute

int solveBrute(int n, vector<int>& heights){

if(n == 0) return 0;

if(n == 1) return abs(heights[1]-heights[0]);

int oneJ = abs(heights[n] - heights[n-1]) + solveBrute(n-1, heights);

int twoJ = abs(heights[n] - heights[n-2]) + solveBrute(n-2, heights);

return min(oneJ, twoJ);

}

//memoization

int solveMemo(int n, vector<int>& heights, vector<int>& dp){

if(n == 0) return 0;

if(n == 1) return abs(heights[1]-heights[0]);

if(dp[n] != -1) return dp[n];

int oneJ = abs(heights[n] - heights[n-1]) + solveMemo(n-1, heights, dp);

int twoJ = abs(heights[n] - heights[n-2]) + solveMemo(n-2, heights, dp);

return dp[n] = min(oneJ, twoJ);

}

//tabulation

int solveTabu(int n, vector<int>& heights){

vector<int> dp(n, 0);

dp[1] = abs(heights[1]-heights[0]);

for(int i=2;i<n;i++){

int oneJ = abs(heights[i] - heights[i-1]) + dp[i-1];

int twoJ = abs(heights[i] - heights[i-2]) + dp[i-2];

dp[i] = min(oneJ, twoJ);

}

return dp[n-1];

}

//space optimisation

int solveSpaceO(int n, vector<int>& heights){

int prev2 = 0, prev1 = abs(heights[1]-heights[0]);

for(int i=2;i<n;i++){

int oneJ = abs(heights[i] - heights[i-1]) + prev1;

int twoJ = abs(heights[i] - heights[i-2]) + prev2;

int curr = min(oneJ, twoJ);

prev2 = prev1;

prev1 = curr;

}

return prev1;

}

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

{

// Write your code here.//

//brute

//return solveBrute(n-1, heights);

//memo

//vector<int> dp(n, -1);

//return solveMemo(n-1, heights, dp);

//tabu

//return solveTabu(n, heights);

//space optz

return solveSpaceO(n, heights);

}

167 views

0 replies

1 upvote

Rohit Saxena

Interview problems

Using memoization

#include <bits/stdc++.h>

int helper(int n , vector<int> &heights , vector<int> &dp) {

if(n == 1) {

return 0;

}

if(dp[n] != -1) {

return dp[n];

}

int jump1 = 0 , jump2 = INT_MAX;

jump1 =abs( heights[n - 1] - heights[n - 2] ) + helper( n - 1 , heights , dp);

if (n - 2 > 0) {

jump2 = abs(heights[n - 1] - heights[n - 3]) + helper(n - 2, heights , dp);

}

dp[n] = min(jump1 , jump2);

return dp[n];

}

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

{

vector<int>dp(n + 1 , -1);

int ans = helper( n, heights, dp);

return ans;

}

171 views

0 replies

0 upvotes

Aman Raj

Interview problems

TC = O(N) SC = O(1)

int frogJump(int n, vector<int> &heights)
{
    // Write your code here. (best possible space optimization)
    int prev1 = 0, prev2 = 0, curr;

    for(int i = 1; i<n; i++){
        int fs = prev1+ abs(heights[i]-heights[i-1]);
        int ss = INT_MAX;
        
        if(i>1)
        ss = prev2+ abs(heights[i]-heights[i-2]);
        curr = min(fs, ss);

        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}

162 views

0 replies

0 upvotes

RAUSHAN KUMAR THAKUR

Interview problems

DP || SPACE OPTIMIZATION || JAVA

import java.util.* ;
import java.io.*; 
public class Solution {

    // Space : O(1);
    // Time : O(n);
    public static int frogJump(int n, int heights[]) {
        int prev2 = -1, prev = 0, curr = 0;
        for (int idx = 1; idx < n; idx++) {
            int left = prev + Math.abs(heights[idx] - heights[idx - 1]);
            int right = Integer.MAX_VALUE;
            if(idx > 1){
                right = prev2 + Math.abs(heights[idx] - heights[idx - 2]);
            }
            curr = Math.min(left, right);

            prev2 = prev;
            prev = curr;
        }
        return prev;
        
    }

}

232 views

0 replies

0 upvotes

Kalpit K

Interview problems

DP || WITH SPACE OPTIMISED

#include <bits/stdc++.h>

// void jump( int n , vector<int> &a , vector<int> &dp,int val)

// {

// if(n==0)

// {dp[0]=0; return;}

// if(n==1)

// {

// dp[1]=a[1]; return;

// }

int frogJump(int n, vector<int> &a)

{

vector<int> dp(n+1);

// dp[0]=0;

long long s=0;

// dp[1]=abs(a[1]-a[0]);

int zero=0,one=abs(a[1]-a[0]);

int ans=0;

for( int i=2 ; i<n ; i++ )

{

ans=min(abs(a[i]-a[i-1])+one, abs(a[i]-a[i-2])+zero);

zero=one;

one=ans;

}

return ans;

}

programming

172 views

0 replies

1 upvote

zublie

Interview problems

DP || MEMOIZATION || Striver || C++ 100% working

#include <bits/stdc++.h>

using namespace std;

int f(int ind, vector<int> &heights, vector<int> &dp) {

if (ind == 0) return 0;

if(dp[ind]!=-1) return dp[ind];

int left = f(ind - 1, heights,dp) + abs(heights[ind] - heights[ind - 1]);

//int right = *max_element(heights.begin(),heights.end());

int right=INT_MAX;

if (ind > 1)

right = f(ind - 2, heights,dp) + abs(heights[ind] - heights[ind - 2]);

return dp[ind]=min(left, right);

}

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

vector<int> dp(n+1,-1);

return f(n-1, heights,dp);

}

280 views

0 replies

1 upvote

Sumeet Pandey

Interview problems

easy cpp solution

#include <bits/stdc++.h>

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

{

// Write your code here.

vector<int> dp(n, 0);

dp[0] = 0;

for (int i = 1; i < n; ++i) {

int oneStep = dp[i-1] + abs(heights[i] - heights[i-1]);

int twoSteps = (i > 1) ? dp[i-2] + abs(heights[i] - heights[i-2]) : INT_MAX;

dp[i] = min(oneStep, twoSteps);

}

return dp[n-1];

}

247 views

0 replies

0 upvotes

Console