Minimum Cost to Reach Every Position solution and explanation
4 more videos on this problem
3502. Minimum Cost to Reach Every Position | Weekly Contest 443 | LeetcodeRapid Syntax · 7:50 · 1K views
3502. Minimum Cost to Reach Every Position (Leetcode Easy)Programming Live with Larry · 3:04 · 340 views
3502. Minimum Cost to Reach Every Position | Leetcode Weekly Contest 443Ujjwal Mishra · 10:13 · 136 views
leetcode 3502 Minimum Cost to Reach Every Position | DP, monotonic stack solutionsCode-Yao · 14:17 · 125 views
LeetCode 3502 Minimum Cost to Reach Every Position [easy] [quicksolve]LeetCoders United · 5:00 · 25 views
The problem
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:
- If they are in front of you, you must pay them
cost[i]to swap with them. - If they are behind you, they can swap with you for free.
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] <= 100
Approach overview
Problem 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.
Solution
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).
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 ansclass Solution {
public int[] minCosts(int[] cost) {
int n = cost.length;
int[] ans = new int[n];
int mi = cost[0];
for (int i = 0; i < n; ++i) {
mi = Math.min(mi, cost[i]);
ans[i] = mi;
}
return ans;
}
}class Solution {
public:
vector<int> minCosts(vector<int>& cost) {
int n = cost.size();
vector<int> ans(n);
int mi = cost[0];
for (int i = 0; i < n; ++i) {
mi = min(mi, cost[i]);
ans[i] = mi;
}
return ans;
}
};function minCosts(cost: number[]): number[] {
const n = cost.length;
const ans: number[] = Array(n).fill(0);
let mi = cost[0];
for (let i = 0; i < n; ++i) {
mi = Math.min(mi, cost[i]);
ans[i] = mi;
}
return ans;
}func minCosts(cost []int) []int {
n := len(cost)
ans := make([]int, n)
mi := cost[0]
for i, c := range cost {
mi = min(mi, c)
ans[i] = mi
}
return ans
}Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Cost to Reach Every Position easy or hard?
Minimum Cost to Reach Every Position is classified as an Easy problem. The challenge is recognizing the greedy observation that a running minimum from earlier positions determines the optimal cost for future positions.
Minimum Cost to Reach Every Position Python/Java solution
The implementation is a short linear scan. Maintain a variable storing the minimum cost seen so far, update the result for each index, and adjust the minimum when a better candidate appears. The same logic works across Python, Java, C++, Go, and TypeScript.
How to solve Minimum Cost to Reach Every Position in O(n)?
Iterate through the array while keeping track of the minimum reachable cost from earlier positions. For each index, compute the cost using the current running minimum and update the minimum if the new position offers a cheaper option. This eliminates the need to check every previous index.
What is the best approach for Minimum Cost to Reach Every Position?
The optimal solution uses a greedy running minimum while scanning the array from left to right. Track the smallest effective cost seen so far and use it to compute the cost for the current index. This reduces the complexity to O(n) time and O(1) extra space.
Is Minimum Cost to Reach Every Position asked at Google/Amazon/Meta?
Array greedy and prefix‑minimum problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem ID may vary, the pattern of maintaining a running minimum during traversal is a common interview theme.
What data structure is used in Minimum Cost to Reach Every Position?
The solution primarily relies on simple array traversal with a running minimum variable. No advanced data structures are required, which keeps the space complexity constant and the implementation straightforward.
What is the time complexity of Minimum Cost to Reach Every Position?
The optimal approach runs in O(n) time because the array is processed in a single pass. Each position is evaluated once while maintaining a running minimum cost. Space complexity remains O(1) since only a few variables are stored.