# Minimum Cost to Reach Every Position
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-cost-to-reach-every-position)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-reach-every-position
**Data structures:** Array
---
## 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 <= 100`
* `1 <= cost[i] <= 100`

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem's logic into code. For each position `i`, it calculates the minimum cost to reach that position by iterating through all possible initial swaps with people at positions `j` where `j <= i`. The cost to reach `i` via an initial swap with person `j` is `cost[j]`, as any subsequent swaps to get to `i` are free. Therefore, we find the minimum among `cost[0], cost[1], ..., cost[i]`.
**Time:** O(n^2), where `n` is the length of the `cost` array. The outer loop runs `n` times, and for each iteration `i`, the inner loop runs `i+1` times. This results in a total of 1 + 2 + ... + n operations, which is proportional to n^2. · **Space:** O(n), where `n` is the length of the `cost` array. This space is required to store the output `answer` array. Excluding the output array, the space complexity is O(1).
**Pros:** Simple to understand and directly follows from the problem's definition.; Guaranteed to be correct and is acceptable for small constraints like `n <= 100`.
**Cons:** Inefficient for large inputs due to its O(n^2) time complexity.; Performs redundant calculations, as the minimum of `cost[0...i-1]` is re-calculated in every iteration of the outer loop.
### Explanation
The fundamental insight is that to reach any position `i`, you must first pay to swap with some person at a position `j` that is less than or equal to `i`. The cost of this initial swap is `cost[j]`. Once you are at position `j`, any person originally at a position `k > j` is now behind you, and you can swap with them for free. This means that after paying `cost[j]`, you can reach position `j` and any position `k > j` (including `i`) at no additional cost. To find the minimum cost to reach position `i`, you simply need to find the minimum cost among all possible initial swaps, which corresponds to `min(cost[0], cost[1], ..., cost[i])`.

This brute-force method implements this by using nested loops. The outer loop iterates through each target position `i` from `0` to `n-1`. For each `i`, the inner loop scans all costs from the beginning of the array up to index `i` to find the minimum one, which is then stored as `answer[i]`.

```java
class Solution {
    public int[] minimumCost(int[] cost) {
        int n = cost.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int minCost = Integer.MAX_VALUE;
            for (int j = 0; j <= i; j++) {
                if (cost[j] < minCost) {
                    minCost = cost[j];
                }
            }
            answer[i] = minCost;
        }
        return answer;
    }
}
```
### Algorithm
- Create an integer array `answer` of size `n`, where `n` is the length of the `cost` array.
- Iterate through each target position `i` from `0` to `n-1`.
- For each `i`, initialize a variable `minCost` to a very large value (e.g., `Integer.MAX_VALUE`).
- Start an inner loop, iterating with an index `j` from `0` up to `i`.
- In the inner loop, compare `cost[j]` with the current `minCost` and update `minCost` if `cost[j]` is smaller.
- After the inner loop completes, `minCost` will hold the minimum value in the subarray `cost[0...i]`.
- Assign this `minCost` to `answer[i]`.
- After the outer loop finishes, return the `answer` array.

## Optimized Single Pass with Running Minimum
This optimized approach avoids the redundant computations of the brute-force method. It recognizes that the minimum cost to reach position `i` is simply the minimum of the cost to reach position `i-1` and the cost of swapping directly with person `i`. This allows us to solve the problem in a single pass through the `cost` array, maintaining a running minimum.
**Time:** O(n), where `n` is the length of the `cost` array. We only need to iterate through the input array once. · **Space:** O(n) for the `answer` array. The auxiliary space used is O(1) for the `minCostSoFar` variable.
**Pros:** Highly efficient, with a linear time complexity of O(n).; Optimal solution for the problem, scalable to much larger inputs.; Simple to implement once the running minimum pattern is identified.
**Cons:** The logic might be slightly less intuitive at first glance compared to the brute-force approach.
### Explanation
This approach is based on the same core logic: `answer[i] = min(cost[0], cost[1], ..., cost[i])`. However, it uses a more efficient computation method. We can observe a recurrence relation:

- `answer[0] = cost[0]`
- `answer[i] = min(min(cost[0], ..., cost[i-1]), cost[i])`

Since `min(cost[0], ..., cost[i-1])` is simply `answer[i-1]`, the relation becomes `answer[i] = min(answer[i-1], cost[i])`.

This means we don't need to rescan the prefix of the array for each element. We can iterate through the `cost` array once, keeping track of the minimum cost seen so far. This running minimum at index `i` is exactly the value we need for `answer[i]`.

```java
class Solution {
    public int[] minimumCost(int[] cost) {
        int n = cost.length;
        int[] answer = new int[n];
        
        if (n == 0) {
            return answer;
        }
        
        int minCostSoFar = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            minCostSoFar = Math.min(minCostSoFar, cost[i]);
            answer[i] = minCostSoFar;
        }
        
        return answer;
    }
}
```
### Algorithm
- Create an integer array `answer` of size `n`.
- Initialize a variable, `minCostSoFar`, to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through the `cost` array with an index `i` from `0` to `n-1`.
- In each iteration, update `minCostSoFar` by taking the minimum of its current value and `cost[i]`.
- Set `answer[i]` to the updated `minCostSoFar`.
- After the loop, return the `answer` array.

# Solutions
### Java

```java
class 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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```