Scale Engineer

Minimum Cost to Reach Every Position

Easy
#3114Time: 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).
Data structures
Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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

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.

Walkthrough

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

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

Complexity

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

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem