Minimum Cost to Reach Every Position

Easy
1849.

Minimum Cost to Reach Every Position

Minimum Cost to Reach Every Position is an easy coding problem on arrays, asked in Amazon interviews.

n people stand in a queue at positions 0 to n - 1, and you join at the very end, at position n. You can move forward by swapping places with someone:

  • swapping with the person at a position in front of you (i smaller than yours) costs cost[i], and you move to position i;
  • people behind you will swap with you for free.

For every position i, find the minimum total cost for you to end up at position i. Return the array answer of length n with those costs.

Example 1

Input
cost = [5,3,4,1,3,2]
Output
[5,3,3,1,1,1]
Explanation
To reach position 2, pay 3 to jump to position 1, then swap backwards with the person at 2 for free.

Example 2

Input
cost = [1,2,4,6,7]
Output
[1,1,1,1,1]
Explanation
Pay 1 to reach the front, then every other position is a free swap backwards.

Example 3

Input
cost = [9]
Output
[9]

Constraints

  • 1 <= n == cost.length <= 100
  • 1 <= cost[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} cost
 * @return {number[]}
 */
var minCosts = function(cost) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost to Reach Every Position — Problem & Solution

Minimum Cost to Reach Every Position solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Minimum Cost to Reach Every Position is an easy coding problem on arrays, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

n people stand in a queue at positions 0 to n - 1, and you join at the very end, at position n. You can move forward by swapping places with someone:

  • swapping with the person at a position in front of you (i smaller than yours) costs cost[i], and you move to position i;
  • people behind you will swap with you for free.

For every position i, find the minimum total cost for you to end up at position i. Return the array answer of length n with those costs.

Example 1

Input: cost = [5,3,4,1,3,2]
Output: [5,3,3,1,1,1]
Explanation: To reach position 2, pay 3 to jump to position 1, then swap backwards with the person at 2 for free.

Example 2

Input: cost = [1,2,4,6,7]
Output: [1,1,1,1,1]
Explanation: Pay 1 to reach the front, then every other position is a free swap backwards.

Example 3

Input: cost = [9]
Output: [9]

Constraints

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

Hints for Minimum Cost to Reach Every Position

  1. Hint 1

    Once you have paid to reach some position j, every position behind j is free.

  2. Hint 2

    So reaching position i costs the cheapest cost[j] over all j <= i.

  3. Hint 3

    That is a running (prefix) minimum.

How to solve Minimum Cost to Reach Every Position

Paying cost[j] puts you at j, after which you can drift backwards to any i >= j for free. So the cost of position i is the minimum of cost[0..i] — a prefix minimum.

Approach

  1. Keep best = cost[0].
  2. For each i, set best = min(best, cost[i]) and write answer[i] = best.
  3. Return answer.

Why it works

Any route to position i must pay for at least one swap forward, landing at some j — and the last paid swap lands at some j <= i (otherwise you would still have to move forward to i, which needs another paid swap). Its cost is at least min(cost[0..i]), and paying exactly that minimum and then swapping back for free achieves it.

Complexity

  • Time — O(n)
  • Space — O(1) besides the output

Pitfalls

  • Position i itself is allowed as the paid swap: answer[i] <= cost[i] always.
  • Do not add costs along the way — one paid swap is enough.

Reference solution

Python

from typing import List

def minCosts(cost: List[int]) -> List[int]:
    answer = []
    best = cost[0]
    for c in cost:
        best = min(best, c)
        answer.append(best)
    return answer

Java

public static int[] minCosts(int[] cost) {
    int[] answer = new int[cost.length];
    int best = cost[0];
    for (int i = 0; i < cost.length; i++) {
        best = Math.min(best, cost[i]);
        answer[i] = best;
    }
    return answer;
}

C++

vector<int> minCosts(vector<int>& cost) {
    vector<int> answer(cost.size());
    int best = cost[0];
    for (size_t i = 0; i < cost.size(); i++) {
        best = min(best, cost[i]);
        answer[i] = best;
    }
    return answer;
}

JavaScript

var minCosts = function(cost) {
    var answer = [], best = cost[0];
    for (var i = 0; i < cost.length; i++) {
        if (cost[i] < best) best = cost[i];
        answer.push(best);
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays