Frog jump with K distances

Frog can jump K distances at a time, return minimum energy to get to last element

Frog Jump with K Distances

Problem Statement

A frog wants to climb a staircase with n steps. You're given an integer array, heights, where heights[i] is the height of the ith step, and an integer k.

To jump from step i to step j, the frog uses abs(heights[i] - heights[j]) energy, where abs() means the absolute difference. From step i, the frog can jump to any step in the range [i + 1, i + k], as long as that step exists.

Return the minimum amount of energy needed for the frog to go from step 0 to step n - 1.

Examples

Example 1

Input: heights = [10, 5, 20, 0, 15], k = 2

Output: 15

Explanation:

• Step 0 → Step 2, cost = abs(10 - 20) = 10
• Step 2 → Step 4, cost = abs(20 - 15) = 5

Total cost = 10 + 5 = 15.

Example 2

Input: heights = [15, 4, 1, 14, 15], k = 3

Output: 2

Explanation:

• Step 0 → Step 3, cost = abs(15 - 14) = 1
• Step 3 → Step 4, cost = abs(14 - 15) = 1

Total cost = 1 + 1 = 2.

Solution

This is a variation of the classic Frog Jump problem, but here the frog can jump up to k steps forward instead of just 1 or 2. We solve it using the same four progressive approaches: plain recursion, memoization, tabulation, and space optimization.

1. Plain Recursion

• We think of the problem backward: to reach step index, the frog must have come from one of the previous k steps (as long as that step exists).
• We try jumping back from every possible distance, from 1 up to k, and recursively calculate the energy needed to reach each of those earlier steps.
• We take whichever option gives the smallest total energy.
• The base case is step 0, which needs 0 energy, since that's where the frog starts.

frogJump(heights, k) {
    function recur(index, n, k) {
      if (index == 0) {
        return 0;
      }

      let minimumEnergy = Infinity;

      for (let i = 1; i <= k; i++) {
        let previousIndex = index - i;

        if (previousIndex >= 0) {
          const difference = Math.abs(heights[index] - heights[previousIndex]);

          let jumpEnergy = recur(previousIndex, heights, k) + difference;
          minimumEnergy = Math.min(minimumEnergy, jumpEnergy);
        }
      }

      return minimumEnergy;
    }

    return recur(heights.length - 1, heights.length, k);
}

This works, but recalculates the same subproblems repeatedly, which becomes slow for larger inputs.

2. Memoization (Top-Down)

We use the same recursive logic, but store each step's result in a dp array the first time we calculate it, so we never have to solve the same subproblem twice.

frogJump(heights, k) {
    function recur(index, n, k) {
      if (index == 0) {
        return 0;
      }

      if (dp[index] !== undefined) {
        return dp[index];
      }

      let minimumEnergy = Infinity;

      for (let i = 1; i <= k; i++) {
        let previousIndex = index - i;

        if (previousIndex >= 0) {
          const difference = Math.abs(heights[index] - heights[previousIndex]);

          let jumpEnergy = recur(previousIndex, heights, k) + difference;

          minimumEnergy = Math.min(minimumEnergy, jumpEnergy);
        }
      }
      dp[index] = minimumEnergy;
      return minimumEnergy;
    }

    let dp = [];
    return recur(heights.length - 1, heights.length, k);
}

• Time Complexity: O(N × k) — where N is the number of steps, since each step checks at most k possible previous steps, and each is only calculated once.
• Space Complexity: O(N)

3. Tabulation (Bottom-Up)

Instead of starting from the last step and recursing backward, we start from step 0 and build our way forward, filling in the dp array as we go.

frogJump(heights, k) {
  let n = heights.length;

  let dp = new Array(n).fill(0);

  for (let index = 1; index < n; index++) {
    let minimumEnergy = Infinity;

    for (let j = 1; j <= k; j++) {
      let previousIndex = index - j;

      if (previousIndex >= 0) {
        const difference = Math.abs(heights[index] - heights[previousIndex]);

        let jumpEnergy = dp[previousIndex] + difference;

        minimumEnergy = Math.min(minimumEnergy, jumpEnergy);
      }
    }
    dp[index] = minimumEnergy;
  }
  return dp[n - 1];
}

• Time Complexity: O(N × k) — each step checks at most k possible jump lengths.
• Space Complexity: O(N) — the dp array stores one value per step, and this approach avoids using any recursion stack.

4. Space Optimization

Looking closely at the tabulation approach, we notice that to calculate dp[index], we only ever need values from the last k steps — nothing further back than that. So instead of keeping the whole array, we only need a small array of size k + 1, and reuse its slots in a rotating fashion.

We do this using the modulo operator (% windowSize), which maps any step index to one of the k + 1 available slots, cycling back around as needed.

frogJump(heights, k) {
    let n = heights.length;
    let windowSize = k + 1;
    let dp = new Array(windowSize).fill(0);

    for (let index = 1; index < n; index++) {
      let minimumEnergy = Infinity;

      for (let j = 1; j <= k; j++) {
        let previousIndex = index - j;

        if (previousIndex >= 0) {
          const previousSlot = previousIndex % windowSize;
          const difference = Math.abs(heights[index] - heights[previousIndex]);

          let jumpEnergy = dp[previousSlot] + difference;

          minimumEnergy = Math.min(minimumEnergy, jumpEnergy);
        }
      }

      const currentSlot = index % windowSize;
      dp[currentSlot] = minimumEnergy;
    }
    return dp[(n - 1) % windowSize];
}

• Space Complexity: O(K)