3502. Minimum Cost to Reach Every Position

Problem Description

You start at position n (the end of a line) in a line of n + 1 people numbered from 0 to n. Your goal is to move forward in the line toward position 0.

You're given an integer array cost of size n, where cost[i] represents the amount person i charges to swap places with you.

The swapping rules are:

If person i is in front of you (has a smaller position number), you must pay them cost[i] to swap places
If person i is behind you (has a larger position number), they can swap with you for free

You need to return an array answer of size n, where answer[i] represents the minimum total cost required to reach position i from your starting position n.

For example, if you want to reach position 2, you need to calculate the minimum cost to move from position n all the way to position 2. Since you can only move forward by swapping with people in front of you (and must pay them), the key insight is that to reach any position i, you only need to pay the minimum cost among all people from position 0 to position i. This is because once you've moved past someone with a lower cost, you can use them to "leapfrog" past more expensive people behind them for free.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Let's think about how we can reach any position i from the end of the line with minimum cost.

Initially, we're at position n. To move forward, we need to swap with people in front of us (positions 0 to n-1), and each swap costs us cost[j] for person j.

Here's the key observation: once we've moved past a person with a low cost, we can use them strategically. Since people behind us can swap with us for free, we can have that low-cost person move back behind us for free, then pay them their low cost to move forward again. This effectively lets us "reuse" the cheapest person we've encountered.

For example, if we've already paid cost[0] = 5 to get past person 0, and later we encounter person 3 with cost[3] = 20, we don't have to pay 20. Instead, we can:

Let person 0 swap behind us for free
Pay person 0 their cost of 5 to move forward past person 3
Now we're past person 3 having only paid 5 instead of 20

This means that to reach any position i, we only need to find the minimum cost among all people from position 0 to position i, and pay that amount once. The person with minimum cost acts as our "helper" who can repeatedly swap behind us for free and then we pay them to move forward.

Therefore, answer[i] = min(cost[0], cost[1], ..., cost[i]).

This explains why the solution simply tracks the minimum cost seen so far as it iterates through the array - that minimum represents the cheapest "helper" we can use to reach each position.

Solution Approach

The implementation is straightforward once we understand that we need to track the minimum cost encountered from position 0 to each position i.

We use a simple greedy approach with the following steps:

Initialize variables:
- Create an answer array ans of size n to store the minimum cost for each position
- Initialize a variable mi with cost[0] to track the minimum cost seen so far
Iterate through each position:
- For each position i from 0 to n-1:
  - Update mi to be the minimum of the current mi and cost[i]: mi = min(mi, cost[i])
  - Set ans[i] = mi, which represents the minimum cost to reach position i
Return the result:
- Return the ans array containing minimum costs for all positions

The algorithm works because:

At position 0, the minimum cost is simply cost[0] since that's the only person we need to pass
At position 1, the minimum cost is min(cost[0], cost[1]) - we use whichever person is cheaper
At position i, the minimum cost is min(cost[0], cost[1], ..., cost[i]) - we use the cheapest person encountered so far

Time Complexity: O(n) - we iterate through the array once
Space Complexity: O(n) - for storing the answer array (or O(1) extra space if we don't count the output array)

This solution elegantly captures the insight that we only need to pay the minimum cost among all people from the start to our target position.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example: cost = [4, 3, 8, 2, 5]

We start at position n = 5 (end of the line). Our goal is to find the minimum cost to reach each position from 0 to 4.

Initial Setup:

People are arranged: [0, 1, 2, 3, 4, You] with costs [4, 3, 8, 2, 5]
We'll track the minimum cost seen so far as mi

Step-by-step calculation:

Position 0:

To reach position 0, we only need to swap with person 0
Person 0 charges cost[0] = 4
mi = 4
answer[0] = 4

Position 1:

To reach position 1, we need to get past persons 0 and 1
We could pay person 0 (cost 4) and person 1 (cost 3) individually = 7 total
OR we can use our key insight: find the cheapest person so far and use them
mi = min(4, 3) = 3
We can pay person 1 (cost 3) to swap, then have them swap back for free, then pay them again to get past person 0
answer[1] = 3

Position 2:

To reach position 2, we need to get past persons 0, 1, and 2
Person 2 charges cost[2] = 8
mi = min(3, 8) = 3 (person 1 is still our cheapest helper)
We use person 1 (cost 3) to leapfrog past everyone
answer[2] = 3

Position 3:

To reach position 3, we need to get past persons 0, 1, 2, and 3
Person 3 charges cost[3] = 2
mi = min(3, 2) = 2 (person 3 becomes our new cheapest helper!)
answer[3] = 2

Position 4:

To reach position 4, we need to get past persons 0, 1, 2, 3, and 4
Person 4 charges cost[4] = 5
mi = min(2, 5) = 2 (person 3 remains our cheapest helper)
We use person 3 (cost 2) to reach position 4
answer[4] = 2

Final Result: answer = [4, 3, 3, 2, 2]

This example demonstrates how we only need to pay the minimum cost among all people from position 0 to our target position i. The person with the minimum cost acts as our reusable helper for all swaps.

Solution Implementation

1class Solution:
2    def minCosts(self, cost: List[int]) -> List[int]:
3        """
4        Calculate the minimum cost seen so far for each position in the array.
5      
6        Args:
7            cost: List of integers representing costs at each position
8          
9        Returns:
10            List where each element i contains the minimum cost from index 0 to i
11        """
12        n = len(cost)
13      
14        # Initialize result array to store minimum costs
15        result = [0] * n
16      
17        # Track the minimum cost seen so far
18        min_cost_so_far = cost[0]
19      
20        # Iterate through each cost and update the minimum
21        for index, current_cost in enumerate(cost):
22            # Update minimum if current cost is smaller
23            min_cost_so_far = min(min_cost_so_far, current_cost)
24          
25            # Store the minimum cost up to this position
26            result[index] = min_cost_so_far
27      
28        return result
29

1class Solution {
2    /**
3     * Calculates the minimum cost encountered up to each index.
4     * For each position i, stores the minimum value among all elements from index 0 to i.
5     * 
6     * @param cost Array of costs
7     * @return Array where ans[i] represents the minimum cost from index 0 to i
8     */
9    public int[] minCosts(int[] cost) {
10        int n = cost.length;
11        int[] result = new int[n];
12      
13        // Initialize minimum with the first element
14        int minSoFar = cost[0];
15      
16        // Iterate through the array to find running minimum
17        for (int i = 0; i < n; i++) {
18            // Update minimum if current element is smaller
19            minSoFar = Math.min(minSoFar, cost[i]);
20          
21            // Store the minimum value up to current index
22            result[i] = minSoFar;
23        }
24      
25        return result;
26    }
27}
28

1class Solution {
2public:
3    vector<int> minCosts(vector<int>& cost) {
4        int n = cost.size();
5        vector<int> result(n);
6      
7        // Track the minimum cost seen so far
8        int minCostSoFar = cost[0];
9      
10        // For each position, store the minimum cost from index 0 to current index
11        for (int i = 0; i < n; ++i) {
12            // Update the running minimum with current element
13            minCostSoFar = min(minCostSoFar, cost[i]);
14          
15            // Store the minimum cost up to index i
16            result[i] = minCostSoFar;
17        }
18      
19        return result;
20    }
21};
22

1/**
2 * Calculates the minimum cost encountered up to each index in the array
3 * @param cost - Array of costs at each position
4 * @returns Array where each element represents the minimum cost from index 0 to that position
5 */
6function minCosts(cost: number[]): number[] {
7    // Get the length of the input array
8    const arrayLength: number = cost.length;
9  
10    // Initialize result array with zeros
11    const result: number[] = Array(arrayLength).fill(0);
12  
13    // Track the minimum value seen so far
14    let minimumValue: number = cost[0];
15  
16    // Iterate through each position in the cost array
17    for (let index: number = 0; index < arrayLength; ++index) {
18        // Update minimum value if current cost is smaller
19        minimumValue = Math.min(minimumValue, cost[index]);
20      
21        // Store the minimum value at current position
22        result[index] = minimumValue;
23    }
24  
25    return result;
26}
27

Time and Space Complexity

The time complexity is O(n), where n is the length of the array cost. The algorithm iterates through the array exactly once using a single for loop with enumerate(cost), performing constant-time operations (comparison with min() and assignment) at each iteration.

The space complexity is O(1) if we exclude the space used by the answer array ans. The algorithm only uses a constant amount of extra space with the variable mi to track the minimum value seen so far. Including the answer array, the total space complexity would be O(n), but following the convention stated in the reference answer, we ignore the space used by the output array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem Direction

A common mistake is confusing the movement direction and payment rules. Students often think:

They need to pay people behind them to move forward
They can swap with people in front for free

The correct understanding: You start at position n and move toward position 0. You pay people who are in front of you (lower position numbers) to swap places.

2. Incorrect Initial Position Assumption

Some implementations incorrectly assume the starting position or try to include cost[n] in calculations:

# WRONG: Trying to use n as an index
min_cost = cost[n]  # IndexError: list index out of range

# WRONG: Starting from the wrong end
for i in range(n-1, -1, -1):
    # Processing backwards doesn't capture the right logic

Solution: Remember that the array has size n, indexed from 0 to n-1, and you start at position n (outside the array).

3. Accumulating Costs Instead of Taking Minimum

A frequent error is summing up all costs encountered rather than keeping only the minimum:

# WRONG: Accumulating costs
result[i] = result[i-1] + cost[i]

# CORRECT: Taking minimum
min_cost_so_far = min(min_cost_so_far, cost[i])
result[i] = min_cost_so_far

4. Off-by-One Errors in Loop Bounds

Incorrect loop boundaries can miss elements or cause index errors:

# WRONG: Missing the last element
for i in range(n-1):  # Should be range(n)
  
# WRONG: Including non-existent index
for i in range(n+1):  # cost array only has n elements

5. Not Handling Edge Cases

Failing to consider special cases like:

Empty array (n = 0)
Single element array (n = 1)

Solution: Add proper validation:

if not cost or len(cost) == 0:
    return []

6. Resetting the Minimum Incorrectly

Some solutions mistakenly reset the minimum for each position instead of maintaining it:

# WRONG: Resetting minimum for each position
for i in range(n):
    min_cost = cost[i]  # This loses previous minimum
  
# CORRECT: Maintaining running minimum
min_cost = cost[0]
for i in range(n):
    min_cost = min(min_cost, cost[i])

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: