DSA

Frog Jump with k distances

Covers: Recursive, Memoized Version, Tabulation version. Optimal — Time O(k*n), Space O(k).

August 8, 2026

DSA Dynamic Programming DP LeetCode Practice

Given an array arr[] of size n, where arr[i] denotes the height of ith stone. Geek starts from stone 0 and from stone i, he can jump to stones i + 1, i + 2, … i + k. The cost for jumping from stone i to stone j is abs(arr[i] – arr[j]). Find the minimum cost for Geek to reach the last stone.

Practice Link

Implementation#

Recursive#

From stone n, the frog could have jumped from any of the k preceding stones. We try all valid reverse jumps, recursing to find the minimum cost to reach each predecessor and adding the height difference for that jump. Without caching, each stone spawns up to k recursive calls, yielding O(k^n) time.

cpp

class Solution {
  public:
  
    int minimizeCostUtil(int k, vector<int>& arr, int n)
    {
        if(n==0)
            return 0;
        
        int minCost = INT_MAX;
        for(int jumpSize = 1;jumpSize<=k;jumpSize++)
        {
            if(n-jumpSize >= 0){
                int jumpCost = minimizeCostUtil(k, arr, n-jumpSize) + abs(arr[n]-arr[n-jumpSize]);
                minCost = min(minCost,jumpCost);
            }
        }
        return minCost;
    }
  
    int minimizeCost(int k, vector<int>& arr) {
        return minimizeCostUtil(k, arr, arr.size()-1);
    }
};

Time Complexity: O(k^n)

Space Complexity: O(n)

Memoized Version#

Cache memo[n] — the minimum cost to reach stone n. Since each stone's minimum cost is computed once and reused, the total work is O(k*n): n stones each scanning up to k predecessors. Space is O(n) for the memo array plus the recursive call stack.

cpp

class Solution {
  public:
  
    int minimizeCostUtil(int k, vector<int>& arr, int n, vector<int> &memo)
    {
        if(n==0)
            return 0;
            
        if(memo[n] != -1)
            return memo[n];
        
        int minCost = INT_MAX;
        for(int jumpSize = 1;jumpSize<=k;jumpSize++)
        {
            if(n-jumpSize >= 0){
                int jumpCost = minimizeCostUtil(k, arr, n-jumpSize, memo) + abs(arr[n]-arr[n-jumpSize]);
                minCost = min(minCost,jumpCost);
            }
        }
        return memo[n] = minCost;
    }
  
    int minimizeCost(int k, vector<int>& arr) {
        vector<int> memo(arr.size(), -1);
        return minimizeCostUtil(k, arr, arr.size()-1, memo);
    }
};

Time Complexity: O(k*n)

Space Complexity: O(n)

Tabulation version#

Build dp[i] — minimum cost to reach stone i — iteratively from i=1 to n-1. For each stone, loop over all k possible predecessors and take the cheapest jump. This bottom-up fill eliminates the recursion stack, keeping O(k*n) time and O(n) space.

cpp

int minimizeCost(int k, vector<int>& arr) {
        int n = arr.size();
        vector<int> dp(n, -1);
        dp[0]=0;

        for(int i=1;i<n;i++)
        {
            int minCost = INT_MAX;
            for(int j=1;j<=k;j++)
            {
                if(i-j>=0)
                {
                    int jumpCost = dp[i-j] + abs(arr[i]-arr[i-j]);
                    minCost = min(minCost,jumpCost);
                }
            }
            dp[i] = minCost;
        }
        return dp[n-1];
        
    }

Time Complexity: O(k*n)

Space Complexity: O(n)

Space Optimized tabulation#

Stone i only reads from its k predecessors, so we keep a circular buffer of size k. The index dp[idx % k] overwrites the value that is no longer needed (it's more than k stones behind). Space drops from O(n) to O(k) with the same O(k*n) time.

Store in a rolling fashion

cpp

class Solution {
public:

    int frogJump(vector<int>& heights, int k) {
        int n = heights.size();
        vector<int> dp(k, 0);

        for(int idx=1; idx<n; idx++)
        {
            int minCost = INT_MAX;
            for(int jumpSize = 1; jumpSize <= k; jumpSize++){
                if(idx-jumpSize >=0 ){
                    int prevIdx = (idx-jumpSize) % k;
                    int jump = abs(heights[idx]- heights[idx-jumpSize]) + dp[prevIdx];
                    minCost = min(minCost, jump);
                }
            }
            dp[idx%k] = minCost;
        }

        return dp[(n-1)%k];
    }
};

Time Complexity: O(k*n)

Space Complexity: O(k)

DSALongest Common Prefix5 approaches incl. Horizontal Scanning, Vertical Scanning, Binary Search, and more. Optimal — Time O(s log m), Space O(1).DSAMaximum Subarray SumCovers: Brute Force, Optimal. Optimal — Time O(n), Space O(1).DSAPalindromic SubstringCovers: Brute Force: generate all su…, Expansion on center, DP. Optimal — Time O(n<sup>2</sup>), Space O(n<sup>2</sup>).