Skip to content

3502. 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.

 

Constraints:

  • 1 <= n == cost.length <= 100
  • 1 <= cost[i] <= 100

Solutions

Solution 1: Brain Teaser

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 \(\textit{mi}\) to record the minimum cost from \(0\) to \(i\).

Starting from \(0\), we iterate through each position \(i\), updating \(\textit{mi}\) as \(\text{min}(\textit{mi}, \text{cost}[i])\) at each step, and assign \(\textit{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 \(\textit{cost}\). Ignoring the space used by the answer array, the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
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

 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 mi = cost[0];
        for (int i = 0; i < n; ++i) {
            mi = Math.min(mi, cost[i]);
            ans[i] = mi;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

Comments