Frog Jump
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 |HEIGHT[i-1] - HEIGHT[j-1] |.In 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.

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

Question

Frog Jump

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 |HEIGHT[i-1] - HEIGHT[j-1] |.In 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.

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

Accepted Answer

Approach :

1) Declare an array ‘DP’ of size N+1.

2) Set DP[N] as 0.

3) Set DP[N-1] as abs(HEIGHTS[N-1] - HEIGHTS[N-2]).

4) For i in range N-2 to 1:
4.1) Set ONE_JUMP as DP[i+1] + abs(HEIGHTS[i-1]-HEIGHTS[i]).
4.2) Set TWO_JUMP as DP[i+2] + abs(HEIGHTS[i-1]-HEIGHTS[i+1]).
4.3) Set DP[i] as the minimum of ONE_JUMP and TWO_JUMP.

5) Set ‘ANS’ as DP[1].

6) Return ANS.

TC : O(N), where N = number of stairs
SC : O(N)

Accepted Answer

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’.

Space Complexity: O(2^n)Explanation:

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).

Time Complexity: O(2^n)Explanation:

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).

Accepted Answer

Top-Down Dynamic Programming

In this approach, we will use the same recursive functions, we used in approach 1 but we will use memoization to reduce the complexity as the answer for each state will be calculated only once.

We will define an array ‘DP’ to store the answers and use them to for further reference.

Algorithm:

Defining 'REC'(i,’ HEIGHTS’ , ‘DP’) function :
- If i equal to the length of ‘HEIGHTS’ - 1:
  - Return 0.
- If DP[i] is not equal to -1:
  - The precomputed value was found.
  - Return DP[i].
- 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,DP).
- If i+2 < length of ‘HEIGHTS’:
  - Set ‘TWO_JUMP’ as abs(HEIGHTS[i]-HEIGHTS[i+2]) + REC(i+2,HEIGHTS,DP).
- Set ‘ANS’ as minimum of ONE_JUMP and TWO_JUMP.
- Set DP[i] as ‘ANS’.
- Return ‘ANS’.
Declare an array DP of size (N+1) to memoize this DP solution.
Set all values of DP to -1.
Set ‘ANS’ as REC(1,HEIGHTS,DP).
Return ‘ANS’.

Space Complexity: O(n)Explanation:

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

In this approach, we are using the ‘DP’ table of size ‘N+1’, and in the worst case, we are making N calls of the 'REC'() function. Hence the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

In this approach, in the worst case, we will run the 'REC' function for all values of DP only once. There are a total of N stairs. Hence the overall time complexity is O(N).

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of staris in the staircase.
*/


public class Solution {

	private static int rec(int i, int heights[], int dp[]) {

		if (i == heights.length - 1){
			// Reached the last stair.
			return 0;
		}
	
		if(dp[i] != -1){
			// Pre-computed value found.
			return dp[i];
		}
	
		// Two available choices.
		int oneJump = Integer.MAX_VALUE;
		int twoJump = Integer.MAX_VALUE;
	
		if (i + 1 < heights.length){
			oneJump = Math.abs(heights[i] - heights[i + 1]) + rec(i + 1, heights, dp);
		}
	
		if (i + 2 < heights.length){
			twoJump = Math.abs(heights[i] - heights[i + 2]) + rec(i + 2, heights, dp);
		}
	
		int ans = Math.min(oneJump, twoJump);
		dp[i] = ans;
		return ans;
	}

	public static int frogJump(int n, int heights[]) {
		int dp[] = new int[n+1];
		for (int i = 0; i <= n;i++){
			dp[i] = -1;
		}
		int ans = rec(0, heights,dp);
		return ans;
	}
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of staris in the staircase.
*/

int inf = 1e9;
int rec(int i, vector &heights, vector &dp){

    if (i == heights.size() - 1){
        // Reached the last stair.
        return 0;
    }

    if(dp[i] != -1){
        // Pre-computed value found.
        return dp[i];
    }

    // Two available choices.
    int oneJump = inf;
    int twoJump = inf;

    if (i + 1 < heights.size()){
        oneJump = abs(heights[i] - heights[i + 1]) + rec(i + 1, heights, dp);
    }

    if (i + 2 < heights.size()){
        twoJump = abs(heights[i] - heights[i + 2]) + rec(i + 2, heights, dp);
    }

    int ans = min(oneJump, twoJump);
    dp[i] = ans;
    return ans;
}

int frogJump(int n, vector &heights)
{
    vector dp(n+1, -1);
    int ans = rec(0, heights, dp);
    return ans;
}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(N)



    where 'N' is the number of staris in the staircase.

"""



from typing import *



inf = 10 ** 9





def rec(i: int, heights: List[int], dp: List[int]) -> int:



    if i == len(heights) - 1:

        # Reached the last stair.

        return 0



    if dp[i] != -1:

        # Pre-computed value found.

        return dp[i]



    # Two available choices.

    oneJump = inf

    twoJump = inf



    if i + 1 < len(heights):

        oneJump = abs(heights[i] - heights[i + 1]) + rec(i + 1, heights, dp)



    if i + 2 < len(heights):

        twoJump = abs(heights[i] - heights[i + 2]) + rec(i + 2, heights, dp)



    ans = min(oneJump, twoJump)

    dp[i] = ans

    return ans





def frogJump(n: int, heights: List[int]) -> int:



    # DP table to memoize the solution.

    dp = [-1 for __ in range(n + 1)]



    ans = rec(0, heights, dp)



    return ans

Accepted Answer

Bottom-Up Dynamic Programming

In this approach, we will make an array DP of size N+1.DP[i] will denote the minimum energy required to reach the last stair from the ith stair.

The base case will be DP[N] should be equal to zero, as the frog is already at the last stair.

DP[N-1] will be abs(HEIGHTS[N-1] - HEIGHTS[N-2] ) as only one jump is possible.

We will run a loop from N-2 to 1 to compute the values of DP[i] as follows:

Choice 1 will be jumping from i to i+1,So DP[i] will be DP[i+1] + abs(HEIGHTS[i-1]- HEIGHTS[i]).

Choice 2 will be jumping form i to i+2,So DP[i] will be DP[i+2] + abs(HEIGHTS[i-1]- HEIGHTS[i+1]).

For all i, we will pick the minimum of these two choices.

At last, we will return DP[1] as the final answer.

Algorithm:

Declare an array ‘DP’ of size N+1.
Set DP[N] as 0.
Set DP[N-1] as abs(HEIGHTS[N-1] - HEIGHTS[N-2]).
For i in range N-2 to 1:
- Set ONE_JUMP as DP[i+1] + abs(HEIGHTS[i-1]-HEIGHTS[i]).
- Set TWO_JUMP as DP[i+2] + abs(HEIGHTS[i-1]-HEIGHTS[i+1]).
- Set DP[i] as the minimum of ONE_JUMP and TWO_JUMP.

Set ‘ANS’ as DP[1].
Return ANS.

Space Complexity: O(n)Explanation:

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

In this approach, we use a ‘DP‘ array of size N+1 to store the DP table. Hence the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

In this approach, we are filling the ‘DP’ of size ‘N to find our final answer. So the overall time complexity is O(N).

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of staris in the staircase.
*/

int frogJump(int n, vector &heights)
{
    vector dp(n+1, -1);

    // Already at last stair.
    dp[n] = 0;

    // Only choice to take a single gap jump.
    dp[n - 1] = abs(heights[n - 2] - heights[n - 1]);

    for(int i = n-2; i > -1; i--){

        int oneJump = dp[i + 1] + abs(heights[i - 1] - heights[i]);
        int twoJump = dp[i + 2] + abs(heights[i - 1] - heights[i + 1]);

        dp[i] = min(oneJump, twoJump);
    }

    int ans = dp[1];
    return ans;
}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(N)



    where 'N' is the number of staris in the staircase.

"""



from typing import *



inf = 10 ** 9





def frogJump(n: int, heights: List[int]) -> int:



    # DP table to memoize the solution.

    dp = [-1 for __ in range(n + 1)]



    # Already at last stair.

    dp[n] = 0



    # Only choice to take a single gap jump.

    dp[n - 1] = abs(heights[n - 2] - heights[n - 1])



    for i in range(n - 2, 0, -1):



        oneJump = dp[i + 1] + abs(heights[i - 1] - heights[i])

        twoJump = dp[i + 2] + abs(heights[i - 1] - heights[i + 1])



        dp[i] = min(oneJump, twoJump)



    ans = dp[1]

    return ans

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of staris in the staircase.
*/

public class Solution {

	public static int frogJump(int n, int heights[]) {
		int dp[] = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			dp[i] = -1;
		}
		// Already at last stair.
		dp[n] = 0;
		// Only choice to take a single gap jump.
		dp[n - 1] = Math.abs(heights[n - 2] - heights[n - 1]);

		for (int i = n - 2; i > 0; i--) {

			int oneJump = dp[i + 1] + Math.abs(heights[i - 1] - heights[i]);
			int twoJump = dp[i + 2] + Math.abs(heights[i - 1] - heights[i + 1]);

			dp[i] = Math.min(oneJump, twoJump);
		}

		int ans = dp[1];
		return ans;
	}
}

For Example

Input Format:

Output Format:

Note:

Constraints:

Top CGI Group Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer

Top HR questions asked in CGI Group Associate Software Engineer