Array Reduction 4: Reduce an Array by Repeatedly Removing the Minimum Pair Sum
Question Details
Problem
Given an integer array, repeatedly perform the following operation until one element remains:
- Find the two smallest elements, remove them, and insert their sum back into the array.
Return the total cost (sum of all inserted sums across all operations).
This is equivalent to building an optimal merge tree (Huffman-style).
python
from typing import List
def array_reduction(nums: List[int]) -> int:
**return** the total cost of all merge operations
pass
Example:
**Input**: [4, 3, 2, 6]
Step 1: merge 2+3=5, cost=5, array=[4,5,6]
Step 2: merge 4+5=9, cost=9, array=[6,9]
Step 3: merge 6+9=15, cost=15, array=[15]
**Output**: 5+9+15 = 29
Approach
Use a min-heap. At each step, pop two smallest elements, compute their sum, accumulate cost, and push the sum back. Time: O(n log n).
Follow-ups
- Why does a greedy min-heap strategy provably minimize total cost here?
- What is the worst-case array that maximizes total cost for a fixed sum of elements?
- How would the answer change if you could merge any k elements (not just 2) at each step?
- How would you reconstruct the merge tree, not just the cost?
Full Details
Problem
Given an integer array, repeatedly perform the following operation until one element remains:
- Find the two smallest elements, remove them, and insert their sum back into the array.
Return the total cost (sum of all inserted sums across all operations).
This is equivalent to building an optimal merge tree (Huffman-style).
python
from typing import List
def array_reduction(nums: List[int]) -> int:
**return** the total cost of all merge operations
pass
Example:
**Input**: [4, 3, 2, 6]
Step 1: merge 2+3=5, cost=5, array=[4,5,6]
Step 2: merge 4+5=9, cost=9, array=[6,9]
Step 3: merge 6+9=15, cost=15, array=[15]
**Output**: 5+9+15 = 29
Approach
Use a min-heap. At each step, pop two smallest elements, compute their sum, accumulate cost, and push the sum back. Time: O(n log n).
Follow-ups
- Why does a greedy min-heap strategy provably minimize total cost here?
- What is the worst-case array that maximizes total cost for a fixed sum of elements?
- How would the answer change if you could merge any k elements (not just 2) at each step?
- How would you reconstruct the merge tree, not just the cost?