Problem

Submissions

Hints & solutions

Discuss

Frog Jump

Easy

0/40

Average time to solve is 30m

Contributed by

739 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

Shuvro Debnath

Interview problems

Best C++ solution...Using dp => memoization, tabulation, tabulation(space optimized)

#include <bits/stdc++.h>

using namespace std;

// int CD(int n, vector<int>&v, vector<int>&dp){

// if(n==0)return 0;

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

// int left=CD(n-1, v, dp)+abs(v[n-1]-v[n]), right=INT_MAX;

// if(n>1){

// right=CD(n-2, v, dp)+abs(v[n-2]-v[n]); ///Using Recursion (memoization)

// }

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

// }

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

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

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

// }

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

// vector<int>dp(n, 0), v;

// v=heights;

// int ans=0;

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

// int left=dp[i-1]+abs(v[i-1]-v[i]), right=INT_MAX; ///Using iteration (tabulation)

// if(i>1)right=dp[i-2]+abs(v[i-2]-v[i]);

// dp[i]=min(left, right);

// }

// return dp[n-1];

// }

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

vector<int>v;

v=heights;

int a1=0, a2, cur;

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

int left=a1+abs(v[i-1]-v[i]), right=INT_MAX;

if(i>1)right=a2+abs(v[i-2]-v[i]);

cur=min(left, right);

a2=a1;

a1=cur;

}

return a1;

}

16 views

0 replies

0 upvotes

Purusharth Agarwal

Interview problems

7-Day Beginner Challenge 23 || 24-Nov-2024 || Frog Jump || Java 17 || TC: O(N) || SC: O(1)

import java.util.* ;
import java.io.*; 
public class Solution {
    public static int frogJump(int n, int heights[]) {
        // Write your code here
        if (n == 1) return 0;
        int prev2 = 0;
        int prev1 = Math.abs(heights[1] - heights[0]);

        for (int i = 2; i < n; i++) {
            int jump1 = prev1 + Math.abs(heights[i] - heights[i - 1]);
            int jump2 = prev2 + Math.abs(heights[i] - heights[i - 2]);
            int current = Math.min(jump1, jump2);

            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

java

datastructures

algorithms

100daysofcode

+1 more

25 views

0 replies

0 upvotes

Dhrub Shaw

Interview problems

java solution using memoization

import java.util.* ;

import java.io.*;

public class Solution {

public static int frogJump(int n, int heights[]) {

// Write your code here..

int no=n-1;

int[] dp=new int[no+1];

Arrays.fill(dp,-1);

return f(no,heights,dp);

}

public static int f(int n,int[] heights,int[] dp)

{

if(n==0)return 0;

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

int right=Integer.MAX_VALUE;

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

if(n>1)

right=f(n-2,heights,dp)+Math.abs(heights[n]-heights[n-2]);

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

}

36 views

0 replies

0 upvotes

simhachalam

Interview problems

easy and optimized solution

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

{

int prev1 = 0,prev2 =0,cur = 0;

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

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

int r= INT_MAX;

if(i>1)

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

cur=min(l,r);

prev2 = prev1;

prev1 = cur;

}

return prev1;

}

55 views

0 replies

0 upvotes

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];

}

217 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);

}

169 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;

}

184 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);

}

177 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;

}

177 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;
}

167 views

0 replies

0 upvotes

Console