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:
cost[i] to swap with them.Return an array answer of size n, where answer[i] is the minimum total cost to reach each position i in the line.
Example 1:
Input: cost = [5,3,4,1,3,2]
Output: [5,3,3,1,1,1]
Explanation:
We can get to each position in the following way:
i = 0. We can swap with person 0 for a cost of 5.i = 1. We can swap with person 1 for a cost of 3.i = 2. We can swap with person 1 for a cost of 3, then swap with person 2 for free.i = 3. We can swap with person 3 for a cost of 1.i = 4. We can swap with person 3 for a cost of 1, then swap with person 4 for free.i = 5. We can swap with person 3 for a cost of 1, then swap with person 5 for free.Example 2:
Input: cost = [1,2,4,6,7]
Output: [1,1,1,1,1]
Explanation:
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 <= 1001 <= cost[i] <= 100Problem Overview: You need the minimum cost required to reach every position in an array. From previously reached positions you can either move step‑by‑step or use a cheaper previously available cost option. The goal is to compute the minimum possible cost for each index efficiently.
Approach 1: Brain Teaser / Running Minimum (O(n) time, O(1) space)
The key observation is that reaching position i either comes from the previous position or from the cheapest position seen earlier. Instead of recomputing costs for every pair of indices, maintain the smallest effective cost encountered so far while iterating from left to right. For each position, update the answer using this running minimum and then update the minimum if the current position provides a cheaper future option. This turns what looks like a dynamic programming or graph relaxation problem into a single linear pass.
The algorithm simply iterates once through the array. At each index, compare the current best cost with the cost derived from the previous position. Because the minimum candidate from earlier indices is always tracked, the optimal value for the current position can be computed in constant time. No additional data structures such as heaps or adjacency lists are needed.
This technique works because the cheapest way to reach any future position must come from the smallest previously achievable cost. By continuously carrying forward this minimum, you avoid nested loops and reduce the complexity from a potential O(n^2) comparison to O(n). Problems like this often appear as simplified greedy or prefix‑minimum patterns within array traversal and lightweight greedy reasoning.
Recommended for interviews: Interviewers expect the linear scan with a running minimum. A brute force approach that checks all previous positions demonstrates the core idea but runs in O(n^2). The optimized greedy observation shows stronger problem‑solving ability and familiarity with prefix minimum patterns commonly used in array problems.
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 mi to record the minimum cost from 0 to i.
Starting from 0, we iterate through each position i, updating mi as min(mi, cost[i]) at each step, and assign mi to the i-th position of the answer array.
Finally, return the answer array.
Time complexity is O(n), where n is the length of the array cost. Ignoring the space used by the answer array, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Check All Previous Positions | O(n^2) | O(1) | Useful for understanding the transition idea by comparing every earlier position |
| Running Minimum / Greedy Brain Teaser | O(n) | O(1) | Best choice for large arrays; single pass with constant memory |
3502. Minimum Cost to Reach Every Position | Weekly Contest 443 | Leetcode • Rapid Syntax • 987 views views
Watch 3 more video solutions →Practice Minimum Cost to Reach Every Position with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor