There is an array of heights corresponding to 'n' stones. You have to reach from stone 1 to stone ‘n’.
From stone 'i', it is possible to reach stones 'i'+1, ‘i’+2… ‘i’+'k' , and the cost incurred will be | Height[i]-Height[j] |, where 'j' is the landing stone.
Return the minimum possible total cost incurred in reaching the stone ‘n’.
For 'n' = 3 , 'k' = 1, height = {2, 5, 2}.
Answer is 6.
Initially, we are present at stone 1 having height 2. We can only reach stone 2 as ‘k’ is 1. So, cost incurred is |2-5| = 3. Now, we are present at stone 2, we can only reach stone 3 as ‘k’ is 1. So, cost incurred is |5-2| = 3. So, the total cost is 6.
The first line contains two integers ‘n’ and 'k', representing the number of stones and maximum possible length of jump.
The second line contains ‘n’ integers, representing heights of stones.
The only line contains a single integer representing the minimum possible total cost incurred in reaching the stone ‘n’.
You don’t need to print anything, it has already been taken care of, just complete the given function.
4 2
10 40 30 10
40
For ‘n’ = 4, 'k' = 2, height = {10, 40, 30, 10}
Answer is 40.
Initially, we are present at stone 1 having height 10. We can reach stone 3 as ‘k’ is 2. So, cost incurred is |10-30| = 20.
Now, we are present at stone 3, we can reach stone 4 as ‘k’ is 2. So, cost incurred is |30-10| = 20. So, the total cost is 40. We can show any other path will lead to greater cost.
5 3
10 40 50 20 60
50
1 <= n <= 10^4
1 <= k <= 100
1 <= height[i] <= 10^4
Time Limit: 1 sec
Check every possible combination.
Recursively check all the possible paths to reach the last stone ‘N’. For each path, calculate the total cost incurred by summing up the absolute differences in the heights of the stones occurring in the path. We then return the minimum cost path as the final answer.
The recursive approach works by checking all the possible jumps that can be made from the current stone i, with 1 <= ‘j’ <= ‘K’. For each jump, calculate the cost incurred and recursively check the next possible jumps until the last stone ‘N’ is reached. Repeat this process for all the possible starting stones and keep track of the minimum cost path.
Algorithm:
Function definition for jump (array Height, N, K, curr):
Function definition for minimizeCost (array Height, N, K):
O(k^n), where ‘n’ is the number of stones and ‘k’ is the maximum number of stones the Geek can jump in a single move.
We are generating all possible sequences of jumps from the starting stone to the final stone, where each sequence consists of ‘k’ jumps. Hence, the overall time complexity of this solution is O(k^n).
O(n), where ‘n’ is the number of stones.
We are recursively calling the same function. Hence, the space complexity is O(n) .
All tags
Sort by
Interview problems
Space Optimized Solution
import java.util.*;
public class Solution {
public static int minimizeCost(int n, int k, int []heights){
int[]prev=new int[k];
for(int i=1;i<n;i++){
int mini=Integer.MAX_VALUE;
for(int j=1;j<=k;j++){
if(i-j>=0){
mini=Math.min(mini,prev[k-j]+Math.abs(heights[i]-heights[i-j]));
}
}
for(int x=1;x<k;x++){
prev[x-1]=prev[x];
}
prev[k-1]=mini;
}
return prev[k-1];
}
}
Interview problems
Space Optimized to O(K)...C++ Solution
int minimizeCost(int n, int k, vector<int> &heights){
vector<int> dp(k, -1);
dp[0] = 0;
for (int i = 1; i < n; i++) {
int mini = INT_MAX;
for (int j = 1; j <= k; j++) {
if (i - j >= 0) {
int ref = dp[(i - j) % k] + abs(heights[i] - heights[i - j]);
mini = min(mini, ref);
}
}
dp[i % k] = mini;
}
return dp[(n - 1) % k];
}
Interview problems
EASY C++ || ALL TEST CASES 👍👍
int help(int idx,int k,vector<int> &heights,vector<int> &dp){
if(idx==0) return 0;
if(dp[idx]!=-1) return dp[idx];
int mini=INT_MAX;
for(int i=1;i<=k;i++){
if(dp[idx]!=-1) return dp[idx];
int l=INT_MAX;
if(idx>=i)
l=help(idx-i,k,heights,dp)+abs(heights[idx]-heights[idx-i]);
mini=min(mini,l);
}
dp[idx]=mini;
return dp[idx];
}
int minimizeCost(int n, int k, vector<int> &height){
vector<int> dp(n,-1);
return help(n-1,k,height,dp);
}
Interview problems
I need help with Space Optimization for this question.
Where should I update the list and what constraints do I need to put? I am confused.
Interview problems
Using DP
public class Solution {
public static int minimizeCost(int n, int k, int []height){
int dp[]=new int[n+1];
dp[0]=0;
for(int i=1; i<n; i++)
{
int mnSteps=Integer.MAX_VALUE;
for(int j=1; j<=k; j++)
{
if(i-j>=0)
{
int left=dp[i-j]+Math.abs(height[i]-height[i-j]);
mnSteps=Math.min(mnSteps, left);
}
}
dp[i]=mnSteps;
}
return dp[n-1];
}
}
Interview problems
Python Frog Jump with K steps
This question is a variation of Frog Jump, it contains k jumps instead of 2.
from typing import *
import math
def minimizeCost(n : int, k : int, heights : List[int]) -> int:
# dp array to store the results of visited indexes...
dp = [-1 for i in range(n)]
# recursive function to calculate all costs...
def checkCost(idx, k, arr):
if idx == 0: return 0
if dp[idx] != -1: return dp[idx]
min_cost = math.inf
for j in range(1, k+1):
if (idx - j) >=0:
cur_cost = checkCost(idx-j, k, arr) + abs(arr[idx] - arr[idx-j])
min_cost = min(min_cost, cur_cost)
dp[idx] = min_cost
return min_cost
return checkCost(n-1, k, heights)
Interview problems
tabulating the answer with k sapce complexity
int minimizeCost(int n, int k, vector<int> &height){
// Write your code here.
//tabulating the answer with k sapce complexity
std::vector<int> prevs(1, 0);
for(int i = 1; i < height.size(); i ++){
int answerTemp = INT_MAX;
int temp;
int sub = -1;
for(int j = prevs.size() - 1; j >= 0; j--){
temp = std::abs(height[i] - height[i + sub]) + prevs[j];
answerTemp = std::min(answerTemp, temp);
sub--;
}
prevs.push_back(answerTemp);
if(prevs.size() > k){
prevs.erase(prevs.begin());
}
}
return prevs[k - 1];
}
auto init = [](){
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
return 0;
} ();Interview problems
CPP Tabulation Method
int minimizeCost(int n, int k, vector<int>&height){
vector<int> dp(n+1,0);
dp[0]=0;
for (int ind=1;ind<n;ind++){
int steps = INT_MAX;
for (int j=1;j<=k;j++){
if (ind - j >= 0) {
int jump = dp[ind - j] + abs(height[ind] - height[ind - j]);
steps = min(jump, steps);
}
}
dp[ind]=steps;
}
return dp[n-1];
}
Interview problems
CPP Memoization Solution
int solveUsingMem(int ind, vector<int>& height, int k, vector<int>&dp) {
if (ind == 0) return 0;
if(dp[ind]!=-1){
return dp[ind];
}
int steps = INT_MAX;
for (int j = 1; j <= k; j++) {
if (ind - j >= 0) {
int jump = solveUsingMem(ind - j, height, k,dp) + abs(height[ind] - height[ind - j]);
steps = min(jump, steps);
}
}
return dp[ind]=steps;
}
int minimizeCost(int n, int k, vector<int> &height){
vector<int>dp(n+1,-1);
return solveUsingMem(n-1,height,k,dp);
}
Interview problems
Minimal Cost || DP || Memoization || Tabulation
//Memoization
// int f(int ind,vector<int>&height,vector<int>&dp,int k){
// if(ind==0){
// return 0;
// }
// if(dp[ind]!=-1) return dp[ind];
// int minSteps=INT_MAX,ans=0;
// for(int j=1;j<=k;j++){
// if(ind-j>=0){
// int jump=f(ind-j,height,dp,k)+abs(height[ind]-height[ind-j]);
// minSteps=min(minSteps,jump);
// }
// }
// return dp[ind]=minSteps;
// }
//Tabulation
int f(int ind,vector<int>&height,vector<int>&dp,int k){
dp[0]=0;
for (int i=1;i<ind;i++){
int mmSteps=INT_MAX;
for(int j=1;j<=k;j++){
if(i-j>=0){
int jump=dp[i-j]+abs(height[i]-height[i-j]);
mmSteps=min(jump,mmSteps);
}
}
dp[i]=mmSteps;
}
return dp[ind-1];
}
int minimizeCost(int n, int k, vector<int> &height){
// Write your code here.
// vector<int>dp(n+1,-1); Memoization
vector<int>dp(n,-1);
// return f(n-1,height,dp,k);Memoization
return f(n,height,dp,k);
}
