Remove Stones to Minimize the Total

You are given an array piles where piles[i] is the number of stones in the ith pile, and an integer k. You must apply exactly k operations. In each operation, you choose any pile and remove floor(piles[i] / 2) stones from it. Return the minimum possible total number of remaining stones.

This is LeetCode 1962: Remove Stones to Minimize the Total, and it is a clean example of the greedy + heap pattern. The problem sounds open-ended, but once you see why the greedy choice works, the solution writes itself.

Why this problem matters

Remove Stones is a great entry point into greedy heap problems. Many interview questions follow this same shape: you have a collection of values, you can perform a limited number of operations, and you want to maximize or minimize some total. The trick is always the same. Use a heap to efficiently grab the best candidate for each operation.

Once you internalize this pattern, problems like Kth Largest Element in an Array and task schedulers start looking familiar.

The key insight

Every operation removes floor(piles[i] / 2) stones from whichever pile you choose. To minimize the total, you want each operation to remove as many stones as possible. Since the removal is proportional to the pile size (half of it, rounded down), you should always target the largest pile.

Think about it: halving a pile of 9 removes 4 stones, but halving a pile of 4 only removes 2. The bigger the pile, the more you gain from halving it. So the greedy strategy is to always pick the max, and a max-heap gives you that in O(log n) time.

The solution

import heapq

def min_stone_sum(piles, k):
    heap = [-p for p in piles]
    heapq.heapify(heap)

    for _ in range(k):
        largest = -heapq.heappop(heap)
        reduced = largest - largest // 2
        heapq.heappush(heap, -reduced)

    return -sum(heap)

Python's heapq is a min-heap, so we negate values to simulate a max-heap. Each iteration pops the largest pile, halves it, and pushes the reduced value back. After k operations, the sum of the heap is the answer.

Step-by-step walkthrough

Let's trace through piles = [5, 4, 9] with k = 2.

Operation 1: The heap pops 9 (the max). We remove floor(9/2) = 4 stones, leaving 5. Push 5 back. The piles are now [5, 4, 5] with total 14.

Operation 2: The heap pops 5 (one of the two tied maxes). We remove floor(5/2) = 2 stones, leaving 3. Push 3 back. The piles are now [3, 4, 5] with total 12.

After 2 operations, the minimum total is 12.

Notice how greedy works here: if we had halved the pile of 4 first instead of 9, we would have removed only 2 stones instead of 4. The max-heap ensures we never make that suboptimal choice.

Complexity analysis

The heap approach costs O(n) for heapify plus O(k log n) for the k pop-and-push operations. Since k can be up to 10^5 and n up to 10^5, this comfortably fits within time limits.

Edge cases

• Single pile: piles = [10], k = 3. You just halve the same pile three times: 10 to 5, 5 to 3, 3 to 2. Total = 2.
• All piles are 1: piles = [1, 1, 1], k = 5. Halving 1 gives floor(1/2) = 0, so nothing changes. Total stays 3.
• k larger than needed: Once every pile is 1, additional operations have no effect. The algorithm handles this naturally since popping 1 and pushing 1 - 0 = 1 is a no-op.
• Large k with one big pile: The pile shrinks rapidly (halving is exponential decay), so even a pile of 10^9 reaches 1 in about 30 operations. Extra k is wasted.
• All piles equal: piles = [6, 6, 6], k = 2. First halve gives [6, 6, 3], second gives [3, 6, 3]. Total = 12. The heap breaks ties arbitrarily, which is fine since tied piles yield the same reduction.

The building blocks

This problem uses the max-heap greedy pattern. The template looks like this:

1. Build a max-heap from the input.
2. For each of the k operations, pop the max, transform it, and push the result back.
3. Return the aggregate (sum, max, etc.) of the final heap.

You will see this same skeleton in problems like:

• Last Stone Weight (LeetCode 1046): pop two largest, push their difference.
• Reduce Array Size to Half (LeetCode 1338): greedily remove the most frequent elements.
• Minimum Cost to Merge Stones: repeatedly merge the smallest groups.

The shared idea is that a heap lets you maintain a dynamic collection where you always need the extreme value, and each operation modifies the collection for the next round.

From understanding to recall

You can probably follow every step of this walkthrough right now. But will you remember the negation trick for Python's min-heap next week? Will you recall that the operation is largest - largest // 2 and not largest // 2?

These small details are exactly what slip away under interview pressure. Spaced repetition closes the gap between "I understand it" and "I can write it cold." You practice writing the heap loop from scratch at increasing intervals, and after a few reps the pattern becomes automatic. The greedy heap template is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems.

Related posts

• Kth Largest Element in an Array - Uses a heap to track the top k elements, same heap mechanics in a selection context
• Daily Temperatures - Another problem where picking the right data structure (monotonic stack) turns a brute force into an elegant single-pass
• Find Peak Element - A different greedy insight where you follow the uphill direction to find a peak in O(log n)