Minimum Cost to Make Stall Prices Equal
A fruit market has several stalls arranged in a row. The price charged by each stall for one fruit basket is given in stallPrices.
A market officer can copy one stall's current price to every stall on its left or right. Updating one stall costs the copied price.
Return the minimum total cost required to give every stall a uniform price.
Minimum Uniform Price Cost
Implement the following method:
int minimumUniformPriceCost( List<Integer> stallPrices )
stallPrices contains the current fruit-basket price at every stall from left to right.- The method returns the minimum total cost needed to make all prices equal.
Price Update Operations
Update Stalls on the Left
Choose a stall at index index and copy its current price to every stall before it.
1 ≤ index < stallPrices.size()- Every position from
0 through index - 1 becomes stallPrices.get(index).
- The operation costs
index * stallPrices.get(index).
Update Stalls on the Right
Choose a stall at index index and copy its current price to every stall after it.
0 ≤ index < stallPrices.size() - 1- Every position from
index + 1 through stallPrices.size() - 1 becomes stallPrices.get(index).
- The operation costs
(stallPrices.size() - 1 - index) * stallPrices.get(index) .
The cost is calculated using the selected stall's price when the operation is performed. You may perform any number of operations, including zero.
Constraints
1 ≤ stallPrices.size() ≤ 1,0001 ≤ stallPrices.get(i) ≤ 100,000 for every 0 ≤ i < stallPrices.size().- The result fits in a Java
int.
Examples
Example 1
minimumUniformPriceCost( stallPrices = [11, 4, 4, 4, 6] )
Output: 8
Copy the price at index 1 to the stall on its left for a cost of 1 * 4 = 4. Then copy the price at index 3 to the stall on its right for another cost of 1 * 4 = 4. The total cost is 8.
Example 2
minimumUniformPriceCost( stallPrices = [5, 5, 12, 5] )
Output: 10
Copy the price at index 1 to every stall on its right. The operation costs 2 * 5 = 10 and makes every price equal to 5.
Example 3
minimumUniformPriceCost( stallPrices = [8, 3, 8, 8] )
Output: 9
Use the price 3 at index 1. Updating the left side costs 1 * 3 = 3, and updating the right side costs 2 * 3 = 6. The total cost is 9.
Example 4
minimumUniformPriceCost( stallPrices = [14, 14, 14] )
Output: 0
All stalls already charge the same price.
Example 5
minimumUniformPriceCost( stallPrices = [18] )
Output: 0
A market containing one stall already has a uniform price.