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
Minimum Cost to Reach Every Position INPUT Position Line (0 to n) 0 1 2 3 YOU cost[] array: 1 i=0 3 i=1 2 i=2 4 i=3 You start at position n=4 Pay cost[i] to swap with person i in front of you Input: cost = [1, 3, 2, 4] ALGORITHM STEPS 1 Initialize DP Start from rightmost pos 2 Track Running Sum sum = cost[i] + sum 3 Compute answer[i] answer[i] = sum (total) 4 Move Left Repeat for i = n-1 to 0 DP Computation (right to left): i=3 i=2 i=1 i=0 cost: 4 2 3 1 sum: 4 6 9 10 Direction: right --> left answer[i] = sum(cost[i..n-1]) FINAL RESULT Minimum cost to reach each position: 10 pos 0 9 pos 1 6 pos 2 4 pos 3 pos 0: 1+3+2+4 = 10 pos 1: 3+2+4 = 9 pos 2: 2+4 = 6 pos 3: 4 = 4 Output: [10, 9, 6, 4] OK - Verified Time: O(n) | Space: O(n) Key Insight: To reach position i, you must pay for ALL swaps from position n-1 down to i (everyone in between). Using a suffix sum from right to left, answer[i] = cost[i] + cost[i+1] + ... + cost[n-1]. TutorialsPoint - Minimum Cost to Reach Every Position | Dynamic Programming (Optimized)
Asked in
Amazon 25 Google 18 Microsoft 12
23.5K Views
Medium Frequency
~15 min Avg. Time
890 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen