Minimum Cost to Reach Every Position - Problem
You are given an integer array cost of size n. You are currently at position n (at the end of the line) in a line of n + 1 people (numbered from 0 to n).
You wish to move forward in the line, but each person in front of you charges a specific amount to swap places. The cost to swap with person i is given by cost[i].
You are allowed to swap places with people as follows:
- If they are in front of you, you must pay them
cost[i]to swap with them - If they are behind you, they can swap with you for free
Return an array answer of size n, where answer[i] is the minimum total cost to reach each position i in the line.
Input & Output
Example 1 — Basic Case
$
Input:
cost = [1,3,2,4]
›
Output:
[10,9,6,4]
💡 Note:
To reach position 0: pay person 3 (cost 4) + person 2 (cost 2) + person 1 (cost 3) + person 0 (cost 1) = 10. To reach position 1: pay person 3 (cost 4) + person 2 (cost 2) + person 1 (cost 3) = 9. To reach position 2: pay person 3 (cost 4) + person 2 (cost 2) = 6. To reach position 3: pay person 3 (cost 4) = 4.
Example 2 — Single Person
$
Input:
cost = [5]
›
Output:
[5]
💡 Note:
Only one person in front. To reach position 0, we need to pay person 0 a cost of 5.
Example 3 — All Same Cost
$
Input:
cost = [2,2,2]
›
Output:
[6,4,2]
💡 Note:
To reach position 0: pay 2+2+2 = 6. To reach position 1: pay 2+2 = 4. To reach position 2: pay 2 = 2.
Constraints
- 1 ≤ cost.length ≤ 105
- 1 ≤ cost[i] ≤ 106
Visualization
Tap to expand
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code