Add 3502_minimum_cost_to_reach_every_position

m3xw3ll · m3xw3ll · commit ad8c85257b94 · 2025-04-12T14:44:26.000+02:00
diff --git a/Algorithms/3502_minimum_cost_to_reach_every_position.md b/Algorithms/3502_minimum_cost_to_reach_every_position.md
@@ -0,0 +1,49 @@
+# [Minimum Cost to Reach Every Position](https://leetcode.com/problems/minimum-cost-to-reach-every-position/description/)
+
+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.
+```
+Solution
+```python
+class Solution:
+    def minCosts(self, cost: List[int]) -> List[int]:
+        min_prefix = [cost[0]]
+        for i in range(1, len(cost)):
+            min_prefix.append(min(min_prefix[-1], cost[i]))
+        return min_prefix
+```
diff --git a/Algorithms/snippets/3502_minimum_cost_to_reach_every_position.py b/Algorithms/snippets/3502_minimum_cost_to_reach_every_position.py
@@ -0,0 +1,8 @@
+def min_costs(cost):
+    min_prefix = [cost[0]]
+    for i in range(1, len(cost)):
+        min_prefix.append(min(min_prefix[-1], cost[i]))
+    return min_prefix
+
+
+print(min_costs([5, 3, 4, 1, 3, 2]))
diff --git a/README.md b/README.md
@@ -795,6 +795,7 @@ To search for a specific problem please use ```STRG + F``` to search for.
 | 3483   | [Unique 3-Digit Even Numbers](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3483_unique_three_digit_even_numbers.md)
 | 3492   | [Maximum Containers on a Ship](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3492_maximum_containers_on_a_ship.md)
 | 3498   | [Reverse Degree of a String](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3498_reverse_degree_of_a_string.md)
+| 3502   | [Minimum Cost to Reach Every Position](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3502_minimum_cost_to_reach_every_position.md)
 
 
 ### Pandas
