FastPrep
Problem · Array

Minimum Cost of Left and Right Propagation

Learn this problem
● MediumAmazon logoAmazonINTERNOA
See Amazon hiring insights

Problem statement

You are given a positive integer array values. You may perform either propagation operation any number of times and in any order:

  • Choose index i and propagate left: replace every element before i with values[i]. This costs i * values[i].
  • Choose index i and propagate right: replace every element after i with values[i]. This costs (n - 1 - i) * values[i].

Return the minimum total cost needed to make every array element equal. You may perform zero operations when the array is already uniform.

Function

minimumPropagationCost(values: int[]) → long

Examples

Example 1

values = [5,2,4]return = 4

Keep the middle value 2, propagate it left for cost 2, and propagate it right for another cost 2.

Example 2

values = [1,1,2,1]return = 2

Keep the first run of two 1s and propagate right from index 1 for cost 2.

Constraints

  • 1 <= values.length <= 100000
  • 1 <= values[i] <= 10^9
  • The answer fits in a signed 64-bit integer.

More Amazon problems

drafts saved locally
public long minimumPropagationCost(int[] values) {
    // Write your code here.
}
values[5,2,4]
expected4
checking account