Frog Jump

Algorithm / Intuition

To determine the minimum energy required for a frog to jump from the first to the last stair, two strategies can be considered: greedy and dynamic programming. The greedy approach is insufficient because the frog's total energy expenditure depends on the path chosen. Opting for the least costly path at each step may lead to more expensive jumps in the future. Therefore, evaluating all possible paths using dynamic programming is necessary to find the optimal solution.

Approach

Define the problem in terms of indices. The array indexes [0, 1, 2, ..., n-1] represent the stairs. The function f(n-1) represents the minimum energy needed to jump from stair 0 to stair n-1. The base case is f(0) = 0.
Explore all possible choices to reach the target stair. The frog can jump either one step or two steps. The cost of each jump is derived from the height array, and the remaining cost is obtained through recursive calls.
Return the minimum energy from the possible choices in Step 2. Since the goal is to minimize the total energy, the function should return the lesser of the two computed energies. At index 1, only one recursive call is possible, as the second choice is not feasible. The base case for this scenario is reaching the 0th stair.

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int frogJump(vector<int>& heights, int ind) {
        // Base case: if the frog is at the first step
        if (ind == 0) return 0;
        
        // Recursively calculate the energy required to
       // jump to the current step from the previous step
        int jumpOne = frogJump(heights, ind - 1) + abs(heights[ind] - heights[ind - 1]);
        
        // Initialize jumpTwo to a large value
        int jumpTwo = INT_MAX;
        
        // If possible, recursively calculate the energy required to
       //  jump to the current step from two steps back
        if (ind > 1) {
            jumpTwo = frogJump(heights, ind - 2) + abs(heights[ind] - heights[ind - 2]);
        }
        
        // Return the minimum energy required to reach the current step
        return min(jumpOne, jumpTwo);
    }

    int frogJump(vector<int>& heights) {
        int n = heights.size();
        return frogJump(heights, n - 1);
    }
};

int main() {
    Solution sol;
    vector<int> heights = {2, 1, 3, 5, 4};
    int result = sol.frogJump(heights);
    cout << "Minimum energy required: " << result << endl;
    return 0;
}
class Solution {
    public int frogJump(int[] heights, int ind) {
        // Base case: if the frog is at the first step
        if (ind == 0) return 0;
        
        // Recursively calculate the energy required to 
        // jump to the current step from the previous step
        int jumpOne = frogJump(heights, ind - 1) + Math.abs(heights[ind] - heights[ind - 1]);
        
        // Initialize jumpTwo to a large value
        int jumpTwo = Integer.MAX_VALUE;
        
        // If possible, recursively calculate the energy required to 
        // jump to the current step from two steps back
        if (ind > 1) {
            jumpTwo = frogJump(heights, ind - 2) + Math.abs(heights[ind] - heights[ind - 2]);
        }
        
        // Return the minimum energy required to reach the current step
        return Math.min(jumpOne, jumpTwo);
    }

    public int frogJump(int[] heights) {
        int n = heights.length;
        return frogJump(heights, n - 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] heights = {2, 1, 3, 5, 4};
        int result = sol.frogJump(heights);
        System.out.println("Minimum energy required: " + result);
    }
}
class Solution:
    # Helper function to compute the minimum energy required recursively
    def _frogJump(self, heights, ind):
        # Base case: if the frog is at the first step
        if ind == 0:
            return 0
        
        # Recursively calculate the energy required to jump to the current step from the previous step
        jumpOne = self._frogJump(heights, ind - 1) + abs(heights[ind] - heights[ind - 1])
        
        # Initialize jumpTwo to a large value
        jumpTwo = float('inf')
        
        # If possible, recursively calculate the energy required to jump to the current step from two steps back
        if ind > 1:
            jumpTwo = self._frogJump(heights, ind - 2) + abs(heights[ind] - heights[ind - 2])
        
        # Return the minimum energy required to reach the current step
        return min(jumpOne, jumpTwo)

    # Main function to calculate the minimum energy required
    def frogJump(self, heights):
        n = len(heights)
        return self._frogJump(heights, n - 1)

# Main function to demonstrate usage
if __name__ == "__main__":
    sol = Solution()
    heights = [2, 1, 3, 5, 4]
    result = sol.frogJump(heights)
    print("Minimum energy required:", result)
class Solution {
    // Helper function to compute the minimum energy required recursively
    _frogJump(heights, ind) {
        // Base case: if the frog is at the first step
        if (ind === 0) {
            return 0;
        }

        // Recursively calculate the energy required to jump to the current step from the previous step
        let jumpOne = this._frogJump(heights, ind - 1) + Math.abs(heights[ind] - heights[ind - 1]);

        // Initialize jumpTwo to a large value
        let jumpTwo = Infinity;

        // If possible, recursively calculate the energy required to jump to the current step from two steps back
        if (ind > 1) {
            jumpTwo = this._frogJump(heights, ind - 2) + Math.abs(heights[ind] - heights[ind - 2]);
        }

        // Return the minimum energy required to reach the current step
        return Math.min(jumpOne, jumpTwo);
    }

    // Main function to calculate the minimum energy required
    frogJump(heights) {
        const n = heights.length;
        return this._frogJump(heights, n - 1);
    }
}

// Main function to demonstrate usage
const sol = new Solution();
const heights = [2, 1, 3, 5, 4];
const result = sol.frogJump(heights);
console.log("Minimum energy required:", result);

Complexity Analysis

Time Complexity: O(2^N), where N is the number of stairs. In each recursive call, there are two choices available that makes the overall time complexity as O(2^N).

Space Complexity: O(N) due to the recursion stack and the storage of intermediate results.

Intuition

To optimize the recursive solution for finding the minimum energy required for a frog to jump between stairs, the memoization approach can be employed. This technique involves storing intermediate results to prevent redundant calculations and enhance efficiency. The thought process is as follows: First, initialize an array to store the results of previously computed steps. Before calculating the energy required for a specific stair, check if it has already been computed. If so, use the stored value, thereby saving time. If not, compute the value as usual and store it in the array before returning it. This approach ensures that each unique computation is performed only once, significantly reducing the overall time complexity.

Memoization Approach

The steps to convert the recursive solution to a memoized one are as follows:

Create an array dp[n] initialized to -1 to store intermediate results.
Before calculating the result for a particular stair, check if it has already been computed by verifying if dp[n] is not -1. If it has been computed, return the stored value.
If the result has not been computed, calculate it using the recursive relation. Before returning the result, store it in the dp array to avoid redundant calculations in the future.

Recursion Tree

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(int ind, vector<int>& heights, vector<int>& dp) {
        // Base case
        if (ind == 0) return 0; 
        // Memoized result
        if (dp[ind] != -1) return dp[ind]; 

        int jumpOne = solve(ind - 1, heights, dp) + abs(heights[ind] - heights[ind - 1]);
        int jumpTwo = INT_MAX;
        if (ind > 1)
            jumpTwo = solve(ind - 2, heights, dp) + abs(heights[ind] - heights[ind - 2]);
        // Store and return result
        return dp[ind] = min(jumpOne, jumpTwo); 
    }

    int frogJump(vector<int>& heights) {
        int n = heights.size();
        vector<int> dp(n, -1);
        // Start solving from the last stair
        return solve(n - 1, heights, dp); 
    }
};

int main() {
    vector<int> heights = {30, 10, 60, 10, 60, 50};
    Solution sol;
    // Output the result
    cout << sol.frogJump(heights) << endl; 
    return 0;
}
import java.util.Arrays;

class Solution {
    private int solve(int ind, int[] heights, int[] dp) {
        // Base case
        if (ind == 0) return 0; 
        // Memoized result
        if (dp[ind] != -1) return dp[ind]; 

        int jumpOne = solve(ind - 1, heights, dp) + Math.abs(heights[ind] - heights[ind - 1]);
        int jumpTwo = Integer.MAX_VALUE;
        if (ind > 1)
            jumpTwo = solve(ind - 2, heights, dp) + Math.abs(heights[ind] - heights[ind - 2]);
        // Store and return result
        return dp[ind] = Math.min(jumpOne, jumpTwo); 
    }

    public int frogJump(int[] heights) {
        int n = heights.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        // Start solving from the last stair
        return solve(n - 1, heights, dp); 
    }

    public static void main(String[] args) {
        int[] heights = {30, 10, 60, 10, 60, 50};
        Solution sol = new Solution();
        // Output the result
        System.out.println(sol.frogJump(heights)); 
    }
}
class Solution:
    def solve(self, ind, heights, dp):
        if ind == 0:
            # Base case
            return 0  
        if dp[ind] != -1:
            # Memoized result
            return dp[ind]  

        jumpOne = self.solve(ind - 1, heights, dp) + abs(heights[ind] - heights[ind - 1])
        jumpTwo = float('inf')
        if ind > 1:
            jumpTwo = self.solve(ind - 2, heights, dp) + abs(heights[ind] - heights[ind - 2])
        # Store and return result
        dp[ind] = min(jumpOne, jumpTwo)  
        return dp[ind]

    def frogJump(self, heights):
        n = len(heights)
        dp = [-1] * n
        # Start solving from the last stair
        return self.solve(n - 1, heights, dp)  

# Testing the solution
if __name__ == "__main__":
    heights = [30, 10, 60, 10, 60, 50]
    sol = Solution()
    # Output the result
    print(sol.frogJump(heights))  

class Solution {
    solve(ind, heights, dp) {
        // Base case
        if (ind === 0) return 0; 
        // Memoized result
        if (dp[ind] !== -1) return dp[ind]; 

        const jumpOne = this.solve(ind - 1, heights, dp) + Math.abs(heights[ind] - heights[ind - 1]);
        let jumpTwo = Infinity;
        if (ind > 1)
            jumpTwo = this.solve(ind - 2, heights, dp) + Math.abs(heights[ind] - heights[ind - 2]);

        // Store and return result
        dp[ind] = Math.min(jumpOne, jumpTwo); 
        return dp[ind];
    }

    frogJump(heights) {
        const n = heights.length;
        const dp = Array(n).fill(-1);
        // Start solving from the last stair
        return this.solve(n - 1, heights, dp); 
    }
}

// Testing the solution
const heights = [30, 10, 60, 10, 60, 50];
const sol = new Solution();
// Output the result
console.log(sol.frogJump(heights)); 

Complexity Analysis

Time Complexity O(N) due to the recursion with memoization and the linear loop for initialization

SpaceComplexity O(N) for the memoization array used to store intermediate results

Tabulation Approach Intuition

To determine the minimum energy required for a frog to jump from the first to the last stair using the tabulation approach, the process involves constructing a table (or array) to store the minimum energy needed to reach each stair. This dynamic programming technique iteratively fills the table based on previously computed values, ensuring that each step is optimally calculated.

The tabulation approach begins by defining an array, dp, where each element represents the minimum energy required to reach the corresponding stair. By iterating through the array and calculating the energy for each jump, the solution can be efficiently derived.

Approach

Step 1: Declare a dp array of size n, where n is the number of stairs.
Step 2: Initialize the base condition: dp[0] = 0, since no energy is required to stay on the first stair.
Step 3: Set up an iterative loop to traverse the array from index 1 to n-1:
- For each index i, calculate the energy required for a one-step jump (jumpOne) and a two-step jump (jumpTwo).
- Update dp[i] with the minimum energy of the two possible jumps: dp[i] = min(jumpOne, jumpTwo).

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int frogJump(vector<int>& heights) {
        int n = heights.size();
        vector<int> dp(n, -1);
        dp[0] = 0; // Base case

        // Iterative calculation
        for (int ind = 1; ind < n; ind++) {
            int jumpOne = dp[ind - 1] + abs(heights[ind] - heights[ind - 1]);
            int jumpTwo = INT_MAX;
            // Store minimum energy for this stair
            if (ind > 1)
                jumpTwo = dp[ind - 2] + abs(heights[ind] - heights[ind - 2]);
            dp[ind] = min(jumpOne, jumpTwo); 
        }
        // Return the minimum energy required to reach the last stair
        return dp[n - 1]; 
    }
};

int main() {
    vector<int> heights = {30, 10, 60, 10, 60, 50};
    Solution sol;
    cout << sol.frogJump(heights) << endl; // Output the result
    return 0;
}
import java.util.Arrays;

class Solution {
    public int frogJump(int[] heights) {
        int n = heights.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        // Base case
        dp[0] = 0; 

        // Iterative calculation
        for (int ind = 1; ind < n; ind++) {
            int jumpOne = dp[ind - 1] + Math.abs(heights[ind] - heights[ind - 1]);
            int jumpTwo = Integer.MAX_VALUE;
            if (ind > 1)
            // Store minimum energy for this stair
                jumpTwo = dp[ind - 2] + Math.abs(heights[ind] - heights[ind - 2]);
            dp[ind] = Math.min(jumpOne, jumpTwo); 
        }
        // Return the minimum energy required to reach the last stair
        return dp[n - 1]; 
    }

    public static void main(String[] args) {
        int[] heights = {30, 10, 60, 10, 60, 50};
        Solution sol = new Solution();
        // Output the result
        System.out.println(sol.frogJump(heights)); 
    }
}
class Solution:
    def frogJump(self, heights):
        n = len(heights)
        dp = [-1] * n
        dp[0] = 0 # Base case

        # Iterative calculation
        for ind in range(1, n):
            jumpOne = dp[ind - 1] + abs(heights[ind] - heights[ind - 1])
            jumpTwo = float('inf')
            if ind > 1:
                jumpTwo = dp[ind - 2] + abs(heights[ind] - heights[ind - 2])
            # Store minimum energy for this stair    
            dp[ind] = min(jumpOne, jumpTwo) 
        # Return the minimum energy required to reach the last stair
        return dp[n - 1] 

# Testing the solution
if __name__ == "__main__":
    heights = [30, 10, 60, 10, 60, 50]
    sol = Solution()
    # Output the result
    print(sol.frogJump(heights)) 
class Solution {
    frogJump(heights) {
        const n = heights.length;
        const dp = Array(n).fill(-1);
        dp[0] = 0; // Base case

        // Iterative calculation
        for (let ind = 1; ind < n; ind++) {
            const jumpOne = dp[ind - 1] + Math.abs(heights[ind] - heights[ind - 1]);
            let jumpTwo = Infinity;
            if (ind > 1)
                jumpTwo = dp[ind - 2] + Math.abs(heights[ind] - heights[ind - 2]);
            // Store minimum energy for this stair
            dp[ind] = Math.min(jumpOne, jumpTwo); 
        }
        // Return the minimum energy required to reach the last stair
        return dp[n - 1]; 
    }
}

// Testing the solution
const heights = [30, 10, 60, 10, 60, 50];
const sol = new Solution();
console.log(sol.frogJump(heights)); // Output the result

Complexity Analysis

Time Complexity: O(N), where n is the number of stairs.

Space Complexity: O(N), due to the storage required for the dp array.

Space-Optimized Approach Intuition

To solve the problem of finding the minimum energy required for a frog to jump from the first to the last stair using a space-optimized approach, the key is to recognize that only the last two computed values are needed at any iteration. This realization allows the solution to avoid maintaining an entire array, thus saving space.

In this approach, instead of storing all computed energy values in an array, the focus is on keeping track of only the most recent two values. Specifically, the energy required to reach the current stair is determined using the energy values from the previous two stairs. This approach simplifies memory usage while maintaining the correctness of the solution. By iteratively updating two variables that represent the energy values of the last two stairs, the minimum energy can be computed efficiently.

Approach

Initialize Variables:
- prev: Represents the energy required to reach the previous stair.
- prev2: Represents the energy required to reach the stair before the previous one.
Iterative Calculation:
- For each stair from the second to the last, compute the energy required based on the values of prev and prev2.
- Update prev and prev2 for the next iteration.

Dry Run

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int frogJump(vector<int>& heights) {
        int n = heights.size();
        int prev = 0, prev2 = 0; // Initialize for base cases

        // Iterative calculation
        for (int i = 1; i < n; i++) {
            int jumpOne = prev + abs(heights[i] - heights[i - 1]);
            int jumpTwo = INT_MAX;
            if (i > 1)
                jumpTwo = prev2 + abs(heights[i] - heights[i - 2]);
            // Minimum energy for current stair    
            int cur_i = min(jumpOne, jumpTwo); 
            // Update previous values
            prev2 = prev; 
            prev = cur_i;
        }
        // Return the minimum energy required to reach the last stair
        return prev; 
    }
};

int main() {
    vector<int> heights = {30, 10, 60, 10, 60, 50};
    Solution sol;
    cout << sol.frogJump(heights) << endl; // Output the result
    return 0;
}
import java.util.Arrays;

class Solution {
    public int frogJump(int[] heights) {
        int n = heights.length;
        int prev = 0, prev2 = 0; // Initialize for base cases

        // Iterative calculation
        for (int i = 1; i < n; i++) {
            int jumpOne = prev + Math.abs(heights[i] - heights[i - 1]);
            int jumpTwo = Integer.MAX_VALUE;
            if (i > 1)
                jumpTwo = prev2 + Math.abs(heights[i] - heights[i - 2]);
                
            // Minimum energy for current stair
            int cur_i = Math.min(jumpOne, jumpTwo); 
            // Update previous values
            prev2 = prev; 
            prev = cur_i;
        }
        // Return the minimum energy required to reach the last stair
        return prev; 
    }

    public static void main(String[] args) {
        int[] heights = {30, 10, 60, 10, 60, 50};
        Solution sol = new Solution();
        // Output the result
        System.out.println(sol.frogJump(heights)); 
    }
}
class Solution:
    def frogJump(self, heights):
        n = len(heights)
        prev = 0
        prev2 = 0 # Initialize for base cases

        # Iterative calculation
        for i in range(1, n):
            jumpOne = prev + abs(heights[i] - heights[i - 1])
            jumpTwo = float('inf')
            if i > 1:
                jumpTwo = prev2 + abs(heights[i] - heights[i - 2])

            # Minimum energy for current stair
            cur_i = min(jumpOne, jumpTwo) 
            # Update previous values
            prev2 = prev 
            prev = cur_i

        # Return the minimum energy required to reach the last stair
        return prev 

# Testing the solution
if __name__ == "__main__":
    heights = [30, 10, 60, 10, 60, 50]
    sol = Solution()
    # Output the result
    print(sol.frogJump(heights)) 
class Solution {
    frogJump(heights) {
        const n = heights.length;
        // Initialize for base cases
        let prev = 0, prev2 = 0; 

        // Iterative calculation
        for (let i = 1; i < n; i++) {
            const jumpOne = prev + Math.abs(heights[i] - heights[i - 1]);
            let jumpTwo = Infinity;
            if (i > 1)
                jumpTwo = prev2 + Math.abs(heights[i] - heights[i - 2]);
            
            // Minimum energy for current stair
            const cur_i = Math.min(jumpOne, jumpTwo);
            // Update previous values
            prev2 = prev; 
            prev = cur_i;
        }
        // Return the minimum energy required to reach the last stair
        return prev; 
    }
}

// Testing the solution
const heights = [30, 10, 60, 10, 60, 50];
const sol = new Solution();
// Output the result
console.log(sol.frogJump(heights)); 

Complexity Analysis

Time Complexity: O(N), where n is the number of stairs.

Space Complexity: O(1), as only two variables are used to store the last two energy values.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Algorithm / Intuition

Approach

Solution

Complexity Analysis

Intuition

Memoization Approach

Recursion Tree

Solution

Complexity Analysis

Tabulation Approach Intuition

Approach

Solution

Complexity Analysis

Space-Optimized Approach Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code