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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5

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

Solution

Method 1 -

Method 1 – Greedy Minimum Cost

Intuition

The key idea is that to reach any position i, you can either pay the cost to swap directly with person i, or reach a previous position for a lower cost and then swap for free with those behind. By always tracking the minimum cost so far, you can efficiently compute the answer for each position.

Approach

  1. Initialize an array ans of size n to store the minimum cost for each position.
  2. Track the minimum cost seen so far as you iterate through the cost array.
  3. For each position i from 0 to n-1:
    • If cost[i] is less than the current minimum, update the minimum.
    • Set ans[i] to the current minimum cost.
  4. Return the ans array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    std::vector<int> minCosts(const std::vector<int>& cost) {
        int n = cost.size();
        std::vector<int> ans(n);
        int minCost = cost[0];
        for (int i = 0; i < n; ++i) {
            if (cost[i] < minCost) minCost = cost[i];
            ans[i] = minCost;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func minCosts(cost []int) []int {
    n := len(cost)
    ans := make([]int, n)
    minCost := cost[0]
    for i := 0; i < n; i++ {
        if cost[i] < minCost {
            minCost = cost[i]
        }
        ans[i] = minCost
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int[] minCosts(int[] cost) {
        int n = cost.length;
        int[] ans = new int[n];
        int minCost = cost[0];
        for (int i = 0; i < n; i++) {
            if (cost[i] < minCost) minCost = cost[i];
            ans[i] = minCost;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minCosts(cost: IntArray): IntArray {
        val n = cost.size
        val ans = IntArray(n)
        var minCost = cost[0]
        for (i in 0 until n) {
            if (cost[i] < minCost) minCost = cost[i]
            ans[i] = minCost
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from typing import List

class Solution:
    def minCosts(self, cost: List[int]) -> List[int]:
        n = len(cost)
        ans: List[int] = [0] * n
        min_cost = cost[0]
        for i in range(n):
            if cost[i] < min_cost:
                min_cost = cost[i]
            ans[i] = min_cost
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn min_costs(cost: Vec<i32>) -> Vec<i32> {
        let n = cost.len();
        let mut ans = vec![0; n];
        let mut min_cost = cost[0];
        for i in 0..n {
            if cost[i] < min_cost {
                min_cost = cost[i];
            }
            ans[i] = min_cost;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minCosts(cost: number[]): number[] {
        const n = cost.length;
        const ans: number[] = new Array(n);
        let minCost = cost[0];
        for (let i = 0; i < n; i++) {
            if (cost[i] < minCost) minCost = cost[i];
            ans[i] = minCost;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We iterate through the cost array once to find the minimum for each position.
  • 🧺 Space complexity: O(n) — We use an extra array to store the answer.