Remove Stones to Minimize the Total Solution

Problem

You have several piles of stones. In each of exactly k operations, you pick any pile and remove half of its stones (rounded down). Your goal is to choose which pile to operate on each time so that the total stones remaining across all piles is as small as possible.

Input: piles = [5, 4, 9], k = 2
Output: 12
Explanation: Remove 4 from the pile of 9 (→ 5), then remove 2 from a pile of 5 (→ 3); remaining piles sum to 3 + 4 + 5 = 12.

Intuition

Each operation removes floor(pile / 2) stones, so a larger pile always yields a larger removal. The greedy choice is clear: always operate on the current largest pile to remove the most stones per step. The challenge is efficiently finding and updating the largest pile after each operation — that's exactly what a max-heap provides.

Approach 1 — Sort Each Iteration

Sort the array in ascending order before each step, then reduce the last (largest) element. Correct but slow: re-sorting k times wastes work because only one element changes per step.

Repeat k times:
- Sort the array in ascending order.
- Reduce the last element: piles[-1] = piles[-1] - piles[-1] // 2.
Return the sum of all piles.

1def minStoneSum(piles: list[int], k: int) -> int:
2    for _ in range(k):
3        piles.sort()
4        largest = piles[-1]
5        piles[-1] = largest - largest // 2  # keep the ceiling, remove the floor
6    return sum(piles)

Time: O(k · n log n) — a full sort for each of the k operations.

Space: O(1) — sorting in-place, no auxiliary structures.

Approach 2 — Max-Heap (Optimal)

Build a max-heap once so the largest pile is always at the top. Each operation is a pop and a push — O(log n) instead of O(n log n). We also track the running total by subtracting only the stones removed each step, avoiding a final O(n) sum over the heap.

Build a max-heap from piles and compute their initial sum.
Repeat k times:
- Pop the largest pile from the heap.
- Compute removed = floor(largest / 2).
- Subtract removed from the running total.
- Push largest - removed back into the heap.
Return the running total.

1import heapq
2
3def minStoneSum(piles: list[int], k: int) -> int:
4    # Python only has min-heap; negate values to simulate max-heap
5    max_heap = [-pile for pile in piles]
6    heapq.heapify(max_heap)
7    total_stones = sum(piles)
8
9    for _ in range(k):
10        largest = -heapq.heappop(max_heap)
11        removed = largest // 2
12        total_stones -= removed                   # update total by the delta, not the new value
13        heapq.heappush(max_heap, -(largest - removed))
14
15    return total_stones

Time: O(n + k log n) — O(n) to build the heap, then O(log n) per operation.

Space: O(n) — the heap holds all n piles.

Complexity Summary

Approach	Time	Space	When to use
Sort Each Iteration	O(k · n log n)	O(1)	Only acceptable when k and n are both tiny
Max-Heap	O(n + k log n)	O(n)	Always — this is the intended solution

Common Mistakes

Computing the remaining pile as pile // 2 — that's the amount removed, not what stays. The pile becomes pile - pile // 2 (the ceiling), not pile // 2 (the floor).
Forgetting to reinsert the reduced pile — after popping the max, you must push the reduced value back. Skipping this silently deletes a pile from the heap.
Sorting once and reusing that order — after reducing the largest element, a smaller pile may now exceed it. The heap handles this automatically; a sorted array does not.
In Python, using heapq without negation — heapq is a min-heap. Pushing raw values makes you pop the smallest pile each time, maximizing the total instead of minimizing it.
Subtracting the wrong quantity from the running total — subtract removed (what was taken), not largest - removed (what remains). Mixing these up produces an answer that is off by the remaining pile size.

Remove Stones to Minimize the Total — Solution