Description
Description
Editorial
Editorial
Solutions
Solutions
Submissions
Submissions
Medium

You are given an integer array nums of length n.

You may perform any of the following operations any number of times, in any order.

  • operation: Choose an index i such that 0 < i < n - 1, and set all elements from index 0 to i - 1 to nums[i]. The cost of this operation is i * nums[i].
  • Suffix operation: Choose an index i such that 0 < i < n - 1, and set all elements from index i + 1 to n - 1 to nums[i]. The cost of this operation is (n - i - 1) * nums[i].

The cost is based on the current value of nums[i] and includes every element in the chosen prefix or suffix, even if it already equals nums[i].

Return the minimum total cost required to make all elements of nums equal.

 

Example 1:

Input: nums = [1,2,3]

Output: 4

Explanation:

One sequence of operations that achieves the minimum cost is as follows:

numsOperationiModified numsCost
[1, 2, 3]Suffix1[1, 2, 2](3 - 1 - 1) * 2 = 2
[1, 2, 2]Prefix1[2, 2, 2]1 * 2 = 2

Hence, the total cost is 2 + 2 = 4.

Example 2:

Input: nums = [3,3,3,6,3,3]

Output: 9

Explanation:

One sequence of operations that achieves the minimum cost is as follows:

numsOperationiModified numsCost
[3, 3, 3, 6, 3, 3]Suffix2[3, 3, 3, 3, 3, 3](6 - 2 - 1) * 3 = 9

Hence, the total cost is 9.

Example 3:

Input: nums = [3,4,4,5,4,4,3]

Output: 20

Explanation:

One sequence of operations that achieves the minimum cost is as follows:

numsOperationiModified numsCost
[3, 4, 4, 5, 4, 4, 3]Prefix4[4, 4, 4, 4, 4, 4, 3]4 * 4 = 16
[4, 4, 4, 4, 4, 4, 3]Suffix5[4, 4, 4, 4, 4, 4, 4](7 - 5 - 1) * 4 = 4

Hence, the total cost is 16 + 4 = 20.

 

Constraints:

  • 3 <= n == nums.length <= 105
  • 1 <= nums[i] <= 109
 
Code
Code
Testcase
Testcase
Test Result
Test Result