Combine Cards Into a Limited Number of Piles at Minimum Cost
Solve this ProblemYou have several piles of cards. Combining two piles costs the total number of cards in them and produces one pile of that size. You don't have to combine everything: you only need to end up with at most a given number of piles. Find the minimum total cost to get there.
Combining the two smallest piles each time is cheapest, since a combined pile is charged again whenever it is combined later. The only change from "merge everything" is when to stop — as soon as the pile count reaches the target. A min-heap gives the two smallest piles in O(log n) instead of two full scans.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ cards.length ≤ 50, 1 ≤ piles ≤ 50 - ◆
1 ≤ cards[i] ≤ 1000 - ◆
Combining two piles of sizes a and b costs a + b and produces one pile of size a + b - ◆
Combine piles until at most "piles" piles remain; return the minimum total cost (0 if there are already at most "piles" piles)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Scan for the Two Smallest Piles Each Round
BruteCombining the two smallest piles is always cheapest: the combined pile is charged again in every later combination it takes part in, so the smallest piles should be buried deepest. Since only n − piles combinations are needed, repeat that many times: scan the whole pool to find and remove the smallest pile, scan again to find and remove the next smallest, add their sum back to the pool, and add it to the total. Each round costs two full scans of the pool.
O(n²)O(n)1class Solution {
2 public int minCombineCost(int[] cards, int piles) {
3 List<Integer> pool = new ArrayList<>();
4 for (int card : cards) pool.add(card);
5 int total = 0;
6 while (pool.size() > piles) {
7 int firstIdx = 0;
8 for (int i = 1; i < pool.size(); i++) {
9 if (pool.get(i) < pool.get(firstIdx)) firstIdx = i;
10 }
11 int first = pool.remove(firstIdx);
12 int secondIdx = 0;
13 for (int i = 1; i < pool.size(); i++) {
14 if (pool.get(i) < pool.get(secondIdx)) secondIdx = i;
15 }
16 int second = pool.remove(secondIdx);
17 pool.add(first + second);
18 total += first + second;
19 }
20 return total;
21 }
22}Optimal — Min-Heap Until Only the Target Piles Remain
OptimalSame greedy rule with a min-heap holding the piles, so the two smallest are found in O(log n) instead of by scanning. The only difference from combining everything into one pile is the stopping condition: keep going while the heap holds more than "piles" piles. Each iteration pops two piles, pushes their combined pile back, and adds its size to the total.
O(n log n)O(n)1class Solution {
2 public int minCombineCost(int[] cards, int piles) {
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int card : cards) heap.offer(card);
5 int total = 0;
6 while (heap.size() > piles) {
7 int joined = heap.poll() + heap.poll();
8 total += joined;
9 heap.offer(joined);
10 }
11 return total;
12 }
13}