Minimum Cost to Reach Every Position — Problem & Solution
Minimum Cost to Reach Every Position solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Cost to Reach Every Position is an easy coding problem on arrays, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
n people stand in a queue at positions 0 to n - 1, and you join at the very end, at position n. You can move forward by swapping places with someone:
- swapping with the person at a position in front of you (
ismaller than yours) costscost[i], and you move to positioni; - people behind you will swap with you for free.
For every position i, find the minimum total cost for you to end up at position i. Return the array answer of length n with those costs.
Example 1
Input: cost = [5,3,4,1,3,2]
Output: [5,3,3,1,1,1]
Explanation: To reach position 2, pay 3 to jump to position 1, then swap backwards with the person at 2 for free.
Example 2
Input: cost = [1,2,4,6,7]
Output: [1,1,1,1,1]
Explanation: Pay 1 to reach the front, then every other position is a free swap backwards.
Example 3
Input: cost = [9]
Output: [9]
Constraints
1 <= n == cost.length <= 1001 <= cost[i] <= 100
Hints for Minimum Cost to Reach Every Position
Hint 1
Once you have paid to reach some position
j, every position behindjis free.Hint 2
So reaching position
icosts the cheapestcost[j]over allj <= i.Hint 3
That is a running (prefix) minimum.
How to solve Minimum Cost to Reach Every Position
Paying cost[j] puts you at j, after which you can drift backwards to any i >= j for free. So the cost of position i is the minimum of cost[0..i] — a prefix minimum.
Approach
- Keep
best = cost[0]. - For each
i, setbest = min(best, cost[i])and writeanswer[i] = best. - Return
answer.
Why it works
Any route to position i must pay for at least one swap forward, landing at some j — and the last paid swap lands at some j <= i (otherwise you would still have to move forward to i, which needs another paid swap). Its cost is at least min(cost[0..i]), and paying exactly that minimum and then swapping back for free achieves it.
Complexity
- Time —
O(n) - Space —
O(1) besides the output
Pitfalls
- Position
iitself is allowed as the paid swap:answer[i] <= cost[i]always. - Do not add costs along the way — one paid swap is enough.
Reference solution
Python
from typing import List
def minCosts(cost: List[int]) -> List[int]:
answer = []
best = cost[0]
for c in cost:
best = min(best, c)
answer.append(best)
return answerJava
public static int[] minCosts(int[] cost) {
int[] answer = new int[cost.length];
int best = cost[0];
for (int i = 0; i < cost.length; i++) {
best = Math.min(best, cost[i]);
answer[i] = best;
}
return answer;
}C++
vector<int> minCosts(vector<int>& cost) {
vector<int> answer(cost.size());
int best = cost[0];
for (size_t i = 0; i < cost.size(); i++) {
best = min(best, cost[i]);
answer[i] = best;
}
return answer;
}JavaScript
var minCosts = function(cost) {
var answer = [], best = cost[0];
for (var i = 0; i < cost.length; i++) {
if (cost[i] < best) best = cost[i];
answer.push(best);
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays