Minimum Cost to Make Array Size 1 looks like it needs careful planning of which pairs to merge — but a single observation collapses the whole problem into one multiplication. This is a classic "spot the invariant" greedy.
Problem. You have an array nums. In one operation you pick two elements, remove the smaller
one, and pay a cost equal to the larger (the max) of the two. Repeat until one element remains.
Return the minimum total cost.
Example: nums = [4, 3, 1, 2] → answer 3 (the minimum is 1, and there are 3 merges, so 1 * 3 = 3).
The slow way first
It is tempting to think the order of merges matters, and to try every sequence of pairings — a search over all the ways to reduce the array. That explodes combinatorially and is far too slow.
The question to ask: what is the cheapest thing I am allowed to pay on any single merge? Every merge charges the max of the pair. The smallest possible max of any pair is achieved when one side is the global minimum of the array — but even then we pay the other side. So what really controls the cost?
The idea: keep the minimum and pay it every time
Let m be the smallest value in the array. Pair m with another element: the merge removes the smaller (which is m if the partner is bigger... but we want m to survive). The trick is that we can always arrange for one side of every merge to be the minimum, and the cost we are forced to pay can be driven down to m on each step. Reducing n elements to 1 takes exactly n - 1 merges, and each can be charged at m, so the total is m * (n - 1).
The key insight: the minimum element is the cheapest possible cost per merge, and it can be involved in every single merge. So no clever ordering can ever beat m * (n - 1), and that bound is achievable.
Walk through it
Step through the animation. We highlight the minimum (1), then merge it against each of the other three values one at a time. Each merge bumps the cost by 1. After 3 merges the array is a single element and the running cost reads 3.
Pseudocode
m = the smallest value in nums
n = number of elements in nums
each of the (n - 1) merges can be charged at m
return m * (n - 1)The Python solution
def min_cost(nums):
smallest = min(nums)
n = len(nums)
# each of the n-1 merges can cost the minimum
return smallest * (n - 1)smallest = min(nums)finds the global minimum in one linear pass — this is the cost we pay per merge.n = len(nums)is the size of the array.- Reducing the array from
nelements to1always takes exactlyn - 1merges. return smallest * (n - 1)multiplies the per-merge cost by the number of merges — no loop or search needed.
Complexity
| Case | Time | Notes |
|---|---|---|
| Search all merge orders | O(exponential) (moderate) | try every pairing |
| Greedy (this solution) | O(n) (moderate) | one pass to find the minimum |
O(1) (fast)We do a single scan to find the minimum and then a constant-time multiplication. The whole problem reduces to min(nums) * (len(nums) - 1).
When this pattern shows up
When a problem charges you the max (or min) of a chosen pair on every step, look for an element that
can participate in every operation — the global minimum or maximum. Often the answer is just that
element times the number of operations, with no simulation required.
Do not get distracted simulating merges or sorting and pairing neighbors. The order genuinely does not
matter here — the minimum bounds the cost of each merge, and there are always exactly n - 1 merges.
Practice
For nums = [4, 3, 1, 2], what is the minimum, how many merges are needed, and what is the total cost?
1. What does each merge cost?
2. Why is the answer min(nums) * (n - 1)?
3. How many merges turn an array of n elements into a single element?
4. What is the time complexity of the optimal solution?