#3502

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Minimum Cost to Reach Every Position

Calculate the minimum swap costs to reach each position in a line using a precise array-driven strategy for efficiency.

Problem Statement

You are standing at the end of a line of n + 1 people, indexed from 0 to n. Each person in front has a swap cost, given by an array cost of length n. You can swap places with someone in front by paying their cost. The goal is to compute the minimum total cost required to reach each position from the start to the end.

Swaps can only move you forward in the line, and the cost for swapping with person i is cost[i]. Once you reach a position with a lower cost, you can move to any later position without additional cost. Determine the minimum cost to reach every position efficiently, applying an array-driven strategy to avoid redundant calculations.

Examples

Example 1

Input: cost = [5,3,4,1,3,2]

Output: [5,3,3,1,1,1]

We can get to each position in the following way:

Example 2

Input: cost = [1,2,4,6,7]

Output: [1,1,1,1,1]

We can swap with person 0 for a cost of 1, then we will be able to reach any position i for free.

Constraints

1 <= n == cost.length <= 100
1 <= cost[i] <= 100

Solution Approach

Iterate Backwards and Track Minimum

Start from the last position and iterate backward through the cost array. Keep a running minimum of the costs encountered. For each position, assign the minimum of the current cost and the running minimum to ensure the least total cost to reach that position.

Update Costs Dynamically

As you move backward, update an output array that stores the minimum cost for each position. At each step, compare the current position's cost with the running minimum. This leverages the array-driven solution pattern and guarantees optimal decisions without revisiting earlier positions.

Leverage Lower Cost Propagation

Once a position with a lower cost is reached, propagate this cost forward for all subsequent positions. This captures the pattern that reaching a cheaper position early eliminates the need to pay higher costs later, minimizing overall swaps.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each position is processed once, and space complexity is O(n) for storing the output array of minimum costs.

What Interviewers Usually Probe

Are you maintaining the minimum cost encountered as you iterate through the array?
Can you explain why swapping to a lower-cost position helps reduce future costs?
How would your approach change if swaps could move backward as well?

Common Pitfalls or Variants

Common pitfalls

Forgetting to update the running minimum at each step, leading to overestimated costs.
Attempting nested loops for each position instead of using a single pass, causing unnecessary time complexity.
Not propagating lower costs forward, missing the free movement to later positions.

Follow-up variants

Allow swapping with multiple people at once, changing the propagation logic of minimum costs.
Modify costs dynamically during swaps, requiring recomputation of minimums on the fly.
Compute minimum cost to reach only a specific subset of positions instead of all positions.

FAQ

What is the main pattern used in Minimum Cost to Reach Every Position?

The problem follows an array-driven solution pattern where you track and propagate the minimum cost to reach each position efficiently.

Why is backward iteration important in this problem?

Iterating backward ensures that the running minimum cost is correctly applied to all earlier positions, avoiding redundant calculations.

Can I use nested loops to compute the minimum cost?

Using nested loops is unnecessary and less efficient; a single backward pass with a running minimum achieves optimal results.

How do lower-cost positions affect the strategy?

Reaching a lower-cost position early allows free movement to subsequent positions, minimizing the total swap cost.

What are the constraints on the input array cost?

The array length n satisfies 1 <= n <= 100, and each cost[i] is between 1 and 100.

terminal

Solution

Solution 1: Brain Teaser

According to the problem description, the minimum cost for each position $i$ is the minimum cost from $0$ to $i$. We can use a variable $\textit{mi}$ to record the minimum cost from $0$ to $i$.

1

2

3

4

5

6

7

8

9

class Solution:
    def minCosts(self, cost: List[int]) -> List[int]:
        n = len(cost)
        ans = [0] * n
        mi = cost[0]
        for i, c in enumerate(cost):
            mi = min(mi, c)
            ans[i] = mi
        return ans

Continue Practicing

#3501 maximize active section with trade ii #3500 minimum cost to divide array into subarrays #3505 minimum operations to make elements within k subarrays equal