We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Reach Every Position

Number: 3832

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

You are given an integer array cost of size n. Starting from position n (the end of a line of n+1 people numbered 0 to n), you want to move forward. To swap positions with someone directly ahead, you must pay that person's cost. However, if someone is 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 position i.

Key Insights

  • The cost to reach a given position depends on the minimum cost of any swap you have made so far.
  • Once you pay the lowest cost among the persons you pass, any position reached by swapping with a person behind you remains free.
  • The problem essentially reduces to computing the running minimum of the cost array.

Space and Time Complexity

Time Complexity: O(n) – We iterate through the array once. Space Complexity: O(n) – We maintain an output array of size n.

Solution

The approach is simple:

  1. Initialize a variable currentMin to keep track of the minimum cost encountered so far.
  2. Iterate through the cost array from index 0 to n-1. For each index, update currentMin = min(currentMin, cost[i]). This currentMin represents the minimum cost needed to reach that position.
  3. Store the currentMin in the answer array at the corresponding index.
  4. Return the answer array.

The key idea is that once you’ve paid the smallest cost, you can swap freely with any person behind; therefore, the running minimum is the optimal cost to reach all positions ahead.

Code Solutions

# Python solution with line-by-line comments
def minCostToReachPositions(cost):
    # Initialize the answer list and set current minimum cost to a large number
    n = len(cost)
    answer = [0] * n
    current_min = float('inf')
    
    # Iterate over each person's cost to move into that position
    for i in range(n):
        # Update the current minimum if the current cost is lower
        current_min = min(current_min, cost[i])
        # The minimum cost to reach position i is the running minimum cost so far
        answer[i] = current_min
        
    return answer

# Example usage
print(minCostToReachPositions([5, 3, 4, 1, 3, 2]))  # Output: [5, 3, 3, 1, 1, 1]
← Back to All Questions