3502. Minimum Cost to Reach Every Position

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

Intuition

In this problem, we aim to find the minimum cost required to reach each position in a line by swapping positions with other people. The key is to understand that, although the direct swap cost with a person is given by cost[i], finding the minimum total cost involves considering all previous costs up to that point.

By maintaining a running minimum mi as we iterate through the cost array, we can efficiently calculate the minimum total cost to reach any given position. For position i, the answer will be the smallest cost encountered from the start of the array up through position i. This approach effectively leverages the cumulative nature of the minimum cost calculation to efficiently solve the problem with a single pass through the list.

Solution Approach

The solution to this problem involves a simple yet effective iteration and comparison method to determine the minimum cost required to reach each position in the line. Here's a step-by-step breakdown of the approach:

Initialize Variables:
- Start by determining the length of the cost array using n = len(cost).
- Create an answer array ans of size n initialized to 0, which will eventually store the minimum costs to reach each respective position.
- Set a variable mi to cost[0], which will hold the running minimum cost encountered thus far.
Iterate Through Costs:
- Iterate through the cost array. For each position i, update mi by comparing it to the current cost c at that position, using the expression mi = min(mi, c).
- Assign the current minimum mi to the i-th position in the ans array: ans[i] = mi.
Return Result:
- After completing the iteration, the ans array contains the minimum cost to reach each position and is returned as the result.

This approach utilizes fundamental array iteration and comparison operations, maintaining a running minimum to achieve the solution efficiently with a time complexity of O(n).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To better understand the solution approach, let's walk through a concrete example. Assume we are given the cost array as follows: cost = [4, 2, 5, 1, 3].

Initialize Variables:
- Determine the length of the cost array: n = 5.
- Create an answer array ans with size n, initialized to [0, 0, 0, 0, 0].
- Set the running minimum cost mi to the first element of the cost array: mi = cost[0] = 4.
Iterate Through Costs:
- Index 0:
  - Current cost is 4.
  - Update mi = min(mi, 4) = 4.
  - Set ans[0] = mi = 4.
  - Updated ans array: [4, 0, 0, 0, 0].
- Index 1:
  - Current cost is 2.
  - Update mi = min(mi, 2) = 2.
  - Set ans[1] = mi = 2.
  - Updated ans array: [4, 2, 0, 0, 0].
- Index 2:
  - Current cost is 5.
  - Update mi = min(mi, 5) = 2.
  - Set ans[2] = mi = 2.
  - Updated ans array: [4, 2, 2, 0, 0].
- Index 3:
  - Current cost is 1.
  - Update mi = min(mi, 1) = 1.
  - Set ans[3] = mi = 1.
  - Updated ans array: [4, 2, 2, 1, 0].
- Index 4:
  - Current cost is 3.
  - Update mi = min(mi, 3) = 1.
  - Set ans[4] = mi = 1.
  - Updated ans array: [4, 2, 2, 1, 1].
Return Result:
- At the end of the iteration, the ans array [4, 2, 2, 1, 1] represents the minimum total cost required to reach each position in the line. This is returned as the final result.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minCosts(self, cost: List[int]) -> List[int]:
5        # Determine the length of the cost list
6        n = len(cost)
7      
8        # Initialize the answer list with zeros
9        ans = [0] * n
10      
11        # Initialize the current minimum with the first element in the list
12        current_min = cost[0]
13      
14        # Iterate over list, updating the current minimum and answer list
15        for i, c in enumerate(cost):
16            # Update current minimum value found so far
17            current_min = min(current_min, c)
18          
19            # Store the current minimum in the answer list at position i
20            ans[i] = current_min
21      
22        # Return the list of minima up to each position
23        return ans
24

1class Solution {
2    public int[] minCosts(int[] cost) {
3        int n = cost.length; // Get the length of the cost array
4        int[] ans = new int[n]; // Initialize an array to store minimum costs
5        int minCost = cost[0]; // Initialize the minimum cost with the first element in the cost array
6
7        // Loop through each element in the cost array
8        for (int i = 0; i < n; ++i) {
9            // Update the minimum cost encountered so far
10            minCost = Math.min(minCost, cost[i]);
11            // Store the current minimum cost in the ans array
12            ans[i] = minCost;
13        }
14      
15        // Return the array containing minimum costs up to each index
16        return ans;
17    }
18}
19

1class Solution {
2public:
3    // This function calculates the minimum cost up to each element in the given cost vector.
4    vector<int> minCosts(vector<int>& cost) {
5        int n = cost.size(); // Get the size of the cost vector
6        vector<int> ans(n); // Initialize a vector to hold the answers, same length as cost vector
7        int currentMin = cost[0]; // Start with the first element as the initial minimum
8      
9        // Iterate over each cost to calculate the minimum cost seen so far
10        for (int i = 0; i < n; ++i) {
11            // Update the minimum cost encountered so far
12            currentMin = min(currentMin, cost[i]);
13            // Set the current element in the answer vector to the minimum cost encountered so far
14            ans[i] = currentMin;
15        }
16      
17        return ans; // Return the vector containing minimum costs up to each index
18    }
19};
20

1function minCosts(cost: number[]): number[] {
2    // Determine the length of the cost array
3    const n = cost.length;
4  
5    // Initialize an array to store the minimum costs up to each index
6    const ans: number[] = Array(n).fill(0);
7  
8    // Set the initial minimum cost as the first element in the cost array
9    let minCost = cost[0];
10  
11    // Iterate through the cost array
12    for (let i = 0; i < n; ++i) {
13        // Update the minimum cost encountered so far
14        minCost = Math.min(minCost, cost[i]);
15      
16        // Store the minimum cost up to current index in the answer array
17        ans[i] = minCost;
18    }
19  
20    // Return the array of minimum costs
21    return ans;
22}
23

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array cost. This is because the algorithm iterates through the array once to compute the result.

Ignoring the space used by the answer array, the space complexity is O(1) since the space used for variables like mi does not depend on the length of the input array cost.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know