LeetCode 3502 - Minimum Cost to Reach Every Position

LeetCode Problem 3502

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

We are given an array cost of length n. There are n + 1 positions in a line, numbered from 0 to n. Initially, we are standing at position n, which means we are at the very end of the line.

To move forward in the line, we can swap positions with other people. The cost of swapping depends on whether that person is currently in front of us or behind us:

• If a person is in front of us, we must pay cost[i] to swap with person i.
• If a person is behind us, swapping with them is free.

For every position i from 0 to n - 1, we must determine the minimum total amount of money needed to eventually stand at position i.

A key detail is that after paying to swap with someone in front of us, our position changes. This can make other people move behind us, allowing future swaps with them at no additional cost.

The input consists of:

• cost[i], the amount person i charges if we swap with them while they are in front of us.

The output should be an array answer where:

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

The constraints are very small:

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

Although the constraints allow even quadratic solutions, understanding the underlying observation leads to a very simple linear solution.

Important edge cases include arrays of length one, strictly increasing costs, strictly decreasing costs, and situations where the cheapest person appears somewhere in the middle of the line. These cases help reveal the key property of the problem.

Approaches

Brute Force

For a target position i, we can consider every possible person j with j <= i as the first person we pay.

Suppose we pay person j. After swapping with them, we immediately move to position j. Since position j is at or before position i, every person from j through i is now behind us or at our position. We can reach position i through free swaps.

Therefore, to reach position i, we only need to choose some person among positions 0 through i and pay their cost once.

A brute-force solution would evaluate every prefix [0..i] and find the minimum value inside that prefix by scanning it. Repeating this for every position gives the correct answer.

The drawback is that for each position we scan all previous positions, resulting in quadratic time complexity.

Key Insight

To reach position i, we only need to pay one person in the prefix 0..i.

Why?

If we pay person j where j <= i, we move directly to position j. Since position i is behind or equal to our current position, we can then reach i using only free swaps.

Therefore, the minimum cost to reach position i is simply:

$$\min(cost[0], cost[1], \dots, cost[i])$$

This means the answer array is just the prefix minimum of the input array.

As we scan from left to right, we maintain the smallest cost seen so far and store it as the answer for the current position.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) excluding output	For each position, scan the entire prefix to find the minimum
Optimal	O(n)	O(1) excluding output	Maintain a running prefix minimum

Algorithm Walkthrough

1. Create an answer array of length n.
2. Maintain a variable minimumCost that stores the smallest cost encountered so far.
3. Initialize minimumCost with cost[0].
4. Traverse the array from left to right.
5. For each position i, update minimumCost as the minimum of its current value and cost[i].
6. Store minimumCost into answer[i].
7. Continue until all positions have been processed.
8. Return the completed answer array.

Why it works

For any target position i, we may choose to pay any person in the prefix 0..i. Paying person j immediately moves us to position j. Since j <= i, position i is no longer in front of us, so we can reach it using free swaps. Thus the optimal strategy is to pay the cheapest person among positions 0 through i. The algorithm maintains exactly this prefix minimum, so every answer is correct.

Python Solution

from typing import List

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

        for value in cost:
            minimum_cost = min(minimum_cost, value)
            answer.append(minimum_cost)

        return answer

The implementation directly follows the prefix minimum observation.

The variable minimum_cost stores the smallest cost seen so far while scanning the array from left to right. For every element, we update this running minimum and append it to the answer array.

Because the minimum value of a prefix can only stay the same or decrease, a single pass is sufficient. Each position receives the minimum value among all costs encountered up to that point, which is exactly the minimum cost required to reach that position.

Go Solution

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

	answer := make([]int, n)
	minimumCost := cost[0]

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

	return answer
}

The Go implementation mirrors the Python solution. A running prefix minimum is maintained while iterating through the slice. Since all values are at most 100, integer overflow is not a concern. The answer slice is preallocated with length n, allowing direct assignment at each index.

Worked Examples

Example 1

Input

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

Processing:

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]

For example, position 5 can be reached by paying person 3 a cost of 1, moving to position 3, and then using free swaps to reach position 5.

Example 2

Input

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

Processing:

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]

Once we pay person 0 a cost of 1, every other position becomes reachable through free swaps.

Complexity Analysis

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

The algorithm processes each element exactly once. Every iteration performs a constant amount of work, consisting of one comparison and one assignment. Aside from the output array required by the problem, only a single variable is used to track the current prefix minimum.

Test Cases

from typing import List

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

        for value in cost:
            minimum_cost = min(minimum_cost, value)
            answer.append(minimum_cost)

        return answer

s = Solution()

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

assert s.minCosts([7]) == [7]                       # Minimum size array
assert s.minCosts([5,4,3,2,1]) == [5,4,3,2,1]      # Strictly decreasing
assert s.minCosts([1,2,3,4,5]) == [1,1,1,1,1]      # Strictly increasing
assert s.minCosts([4,4,4,4]) == [4,4,4,4]          # All equal values
assert s.minCosts([9,2,8,1,7]) == [9,2,2,1,1]      # Multiple minimum updates
assert s.minCosts([10,1,10,10,10]) == [10,1,1,1,1] # Early minimum dominates
assert s.minCosts([3,1,2,1,5]) == [3,1,1,1,1]      # Repeated minimum values

Test Summary

Test	Why
[5,3,4,1,3,2]	Validates the first example
[1,2,4,6,7]	Validates the second example
[7]	Smallest allowed input
[5,4,3,2,1]	Prefix minimum changes every step
[1,2,3,4,5]	Prefix minimum never changes
[4,4,4,4]	Handles duplicate values
[9,2,8,1,7]	Multiple decreases in minimum
[10,1,10,10,10]	Early minimum dominates all later positions
[3,1,2,1,5]	Repeated occurrences of the same minimum

Edge Cases

Single Element Array

When n = 1, there is only one person in front of us. The answer must simply be [cost[0]]. Implementations that assume multiple elements or incorrectly initialize the running minimum can fail here. The presented solution handles this naturally because the loop processes exactly one value.

Strictly Increasing Costs

Consider cost = [1,2,3,4,5]. The cheapest person appears at the beginning. Once we pay that person, every later position becomes reachable for free. The answer should therefore be [1,1,1,1,1]. This case verifies that the algorithm correctly preserves the smallest prefix value rather than using the current value.

Strictly Decreasing Costs

Consider cost = [5,4,3,2,1]. Every new position introduces a cheaper option than all previous positions. The prefix minimum changes at every step, producing [5,4,3,2,1]. This validates that the running minimum is updated correctly during traversal.

Repeated Minimum Values

Consider cost = [3,1,2,1,5]. The minimum value appears multiple times. The correct answer remains [3,1,1,1,1]. The algorithm works correctly because it only needs to track the minimum value itself, not the position where that minimum first appeared.

Minimum Cost Appearing in the Middle

Consider cost = [8,7,1,9,10]. The cheapest person is neither first nor last. Once position 2 is reached, all subsequent answers should remain 1. This case demonstrates the central insight that the answer for each index is simply the minimum cost within its prefix.