LeetCode 3502 - Minimum Cost to Reach Every Position

LeetCode Problem 3502

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

You are given an array cost where cost[i] represents how much person i charges if you want to swap places with them while they are in front of you.

Initially, you stand at position n, which is the very end of a line containing positions 0 through n. Your goal is to determine the minimum cost required to reach every position i from 0 to n - 1.

The swapping rules are unusual:

• If a person is in front of you, swapping with them costs cost[i].
• If a person is behind you, swapping with them is free.

The key detail is that once you pay to move ahead of someone, that person becomes behind you. Any future swaps involving that person can then be performed for free.

The output should be an array answer where:

• answer[i] is the minimum total cost required to reach position i.

The constraints are very small:

• 1 <= n <= 100
• 1 <= cost[i] <= 100

Even though the constraints are tiny, the goal is to find the underlying pattern and derive the simplest optimal solution.

Important edge cases include:

• A single-element array.
• Costs that are strictly increasing.
• Costs that are strictly decreasing.
• Multiple positions sharing the same minimum cost.
• The minimum cost appearing late in the array.

Understanding how free backward swaps work is the critical part of solving the problem correctly.

Approaches

Brute Force

For each target position i, we could try every possible person j that we might pay to swap with first.

If we pay person j, we immediately move to position j. After that, every person with index greater than or equal to j is behind us, so moving among those positions becomes free.

Therefore, position i is reachable after paying person j if and only if j <= i.

For each position i, we could examine all valid j from 0 through i and choose the smallest cost among them.

This produces the correct answer because every valid way to reach position i must involve paying some person at or before position i, and the cheapest such payment is always optimal.

However, this approach performs a nested scan and requires examining all previous positions for every index.

Key Insight

To reach position i, you only need to pay one person among indices 0 through i.

Suppose you pay person j.

• Cost paid = cost[j].
• You move to position j.
• Every position k >= j is now behind you.
• Moving from position j to any position i >= j is free.

Therefore, reaching position i only requires choosing the cheapest person among positions 0...i.

This means:

$$answer[i] = \min(cost[0], cost[1], \ldots, cost[i])$$

Instead of recomputing this minimum repeatedly, we can maintain a running prefix minimum while scanning from left to right.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) extra	For each position, scan all previous positions to find the minimum cost
Optimal	O(n)	O(1) extra	Maintain a running prefix minimum

Algorithm Walkthrough

1. Create an output array of length n.
2. Initialize a variable min_cost with a very large value.
3. Traverse the array from left to right.
4. For each position i, update:

min_cost = min(min_cost, cost[i])

This maintains the minimum cost seen among positions 0...i. 5. Store min_cost into answer[i]. 6. Continue until all positions have been processed. 7. Return the completed answer array.

Why it works

For any target position i, the first paid swap must be with some person j ≤ i. After paying that person, you stand at position j, and all positions from j onward become reachable for free because those people are now behind you. Therefore, the minimum cost to reach position i is exactly the minimum value among cost[0...i]. The algorithm maintains this prefix minimum incrementally, so every answer is computed correctly.

Python Solution

from typing import List

class Solution:
    def minCosts(self, cost: List[int]) -> List[int]:
        answer = []
        min_cost = float("inf")

        for c in cost:
            min_cost = min(min_cost, c)
            answer.append(min_cost)

        return answer

The implementation follows the prefix-minimum observation directly.

The variable min_cost stores the smallest cost encountered so far. As we iterate through the array, we update this running minimum using the current value.

After updating the minimum, we append it to the answer array. At index i, this minimum represents the smallest value among cost[0...i], which is exactly the minimum cost required to reach position i.

The solution performs a single pass through the input and uses only a few extra variables.

Go Solution

func minCosts(cost []int) []int {
	n := len(cost)
	answer := make([]int, n)

	minCost := cost[0]

	for i := 0; i < n; i++ {
		if cost[i] < minCost {
			minCost = cost[i]
		}
		answer[i] = minCost
	}

	return answer
}

The Go implementation is nearly identical to the Python version.

Since the constraints guarantee at least one element, we can safely initialize minCost with cost[0].

The result is stored in a slice of length n, and a single left-to-right pass maintains the running prefix minimum. Integer overflow is not a concern because all values are at most 100.

Worked Examples

Example 1

Input:

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

Process the array while maintaining the running minimum.

i	cost[i]	Running Minimum	answer
0	5	5	[5]
1	3	3	[5,3]
2	4	3	[5,3,3]
3	1	1	[5,3,3,1]
4	3	1	[5,3,3,1,1]
5	2	1	[5,3,3,1,1,1]

Final result:

[5,3,3,1,1,1]

Example 2

Input:

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

i	cost[i]	Running Minimum	answer
0	1	1	[1]
1	2	1	[1,1]
2	4	1	[1,1,1]
3	6	1	[1,1,1,1]
4	7	1	[1,1,1,1,1]

Final result:

[1,1,1,1,1]

Because the cheapest person is at position 0, paying them once allows every later position to be reached without additional cost.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1) extra	Only the running minimum is maintained, excluding the output array

The algorithm scans the array exactly once. Every iteration performs a constant amount of work, consisting of one comparison and one assignment. No auxiliary data structures are required beyond the output array itself.

Test Cases

sol = Solution()

assert sol.minCosts([5,3,4,1,3,2]) == [5,3,3,1,1,1]  # example 1
assert sol.minCosts([1,2,4,6,7]) == [1,1,1,1,1]      # example 2

assert sol.minCosts([7]) == [7]                       # single element
assert sol.minCosts([5,4,3,2,1]) == [5,4,3,2,1]      # strictly decreasing
assert sol.minCosts([1,2,3,4,5]) == [1,1,1,1,1]      # strictly increasing
assert sol.minCosts([3,3,3,3]) == [3,3,3,3]          # all equal
assert sol.minCosts([8,2,7,1,6]) == [8,2,2,1,1]      # minimum appears later
assert sol.minCosts([10,1,10,1,10]) == [10,1,1,1,1]  # repeated minima
assert sol.minCosts([100,100,100]) == [100,100,100]  # maximum constraint values

Test Summary

Test	Why
[5,3,4,1,3,2]	Validates the first official example
[1,2,4,6,7]	Validates the second official example
[7]	Smallest possible input
[5,4,3,2,1]	Prefix minimum changes every step
[1,2,3,4,5]	Prefix minimum never changes
[3,3,3,3]	Duplicate values throughout
[8,2,7,1,6]	Minimum appears later in the array
[10,1,10,1,10]	Repeated occurrences of the minimum
[100,100,100]	Tests upper bound values

Edge Cases

Single Element Array

When n = 1, there is only one person in front of you. The answer must simply be that person's cost. A buggy implementation might incorrectly assume there are multiple elements or mishandle initialization. The running-minimum approach naturally returns [cost[0]].

Strictly Increasing Costs

Consider cost = [1,2,3,4,5]. Once you pay the first person, every later position becomes reachable for free. Therefore every answer should be 1. Implementations that misunderstand the free-swap rule may incorrectly return the original array instead of the prefix minimums.

Strictly Decreasing Costs

Consider cost = [5,4,3,2,1]. Each new position introduces a cheaper option than all previous positions. The prefix minimum changes at every step, so the answer becomes [5,4,3,2,1]. This case verifies that the running minimum is updated correctly at every iteration.

Minimum Cost Appears Late

Consider cost = [8,7,6,1,9]. Before reaching index 3, the minimum cost keeps decreasing. Once the value 1 is encountered, every later answer should remain 1. This tests whether the algorithm correctly propagates the best cost forward through the remainder of the array.