#1962

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Remove Stones to Minimize the Total

Minimize the total stones by repeatedly removing half from the largest pile using a greedy heap strategy.

Problem Statement

Given an array piles where piles[i] is the number of stones in the ith pile and an integer k, perform exactly k operations. In each operation, choose any pile and remove floor(piles[i]/2) stones from it. You may choose the same pile multiple times.

Return the minimum total number of stones remaining across all piles after exactly k operations. Ensure your approach consistently targets the largest pile each time to maintain correctness with the greedy pattern.

Examples

Example 1

Input: piles = [5,4,9], k = 2

Output: 12

Steps of a possible scenario are:

Apply the operation on pile 2. The resulting piles are [5,4,5].
Apply the operation on pile 0. The resulting piles are [3,4,5]. The total number of stones in [3,4,5] is 12.

Example 2

Input: piles = [4,3,6,7], k = 3

Output: 12

Steps of a possible scenario are:

Apply the operation on pile 2. The resulting piles are [4,3,3,7].
Apply the operation on pile 3. The resulting piles are [4,3,3,4].
Apply the operation on pile 0. The resulting piles are [2,3,3,4]. The total number of stones in [2,3,3,4] is 12.

Constraints

1 <= piles.length <= 105
1 <= piles[i] <= 104
1 <= k <= 105

Solution Approach

Use a Max-Heap for Efficient Selection

Push all piles into a max-heap so the largest pile is always accessible. This allows each greedy choice to be performed in O(log n) time and ensures you always reduce the pile that contributes most to the total.

Apply k Operations

Iteratively remove the maximum pile from the heap, reduce it by floor(pile/2), and push it back. Repeat exactly k times. This directly enforces the greedy choice plus invariant validation pattern by always handling the largest current pile.

Compute the Remaining Total

After completing k operations, sum all remaining piles from the heap to get the minimum possible total stones. This final sum reflects the optimal sequence of reductions guaranteed by the heap-based greedy approach.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + k log n), where n is the number of piles and k is the number of operations, due to heap operations each step. Space complexity is O(n) for storing the heap.

What Interviewers Usually Probe

Are you consistently selecting the pile with the maximum stones each operation?
Do you validate that the total reduces optimally after each step?
Can your approach handle large piles arrays efficiently without scanning all piles every time?

Common Pitfalls or Variants

Common pitfalls

Not using a heap and scanning the array every operation leads to TLE for large inputs.
Incorrectly computing floor division, causing off-by-one errors in stone removal.
Failing to handle repeated operations on the same pile, which violates the greedy invariant.

Follow-up variants

Instead of floor division, remove a fixed number of stones each operation and minimize total.
Perform operations only on piles above a certain threshold, adding a conditional greedy selection.
Maximize the total stones removed instead of minimizing the remaining total, using similar heap logic.

FAQ

What is the main pattern to solve Remove Stones to Minimize the Total?

The problem follows a greedy choice plus invariant validation pattern, where each operation should target the largest current pile.

Can the same pile be chosen multiple times?

Yes, selecting the same pile multiple times is allowed and often necessary to reach the minimal total.

Why is a max-heap preferred for this problem?

A max-heap ensures each operation efficiently selects the largest pile, maintaining the greedy invariant and reducing time complexity.

How do you handle large arrays within constraints?

Using a heap avoids repeated full-array scans, giving O(log n) per operation, which scales to arrays up to 10^5 piles.

What is the key failure mode to watch for?

Failing to always pick the current largest pile or miscomputing floor division can prevent achieving the minimum total.

terminal

Solution

Solution 1: Greedy + Priority Queue (Max Heap)

According to the problem description, in order to minimize the total number of remaining stones, we need to remove as many stones as possible from the stone piles. Therefore, we should always choose the pile with the most stones for removal.

1

2

3

4

5

6

7

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        pq = [-x for x in piles]
        heapify(pq)
        for _ in range(k):
            heapreplace(pq, pq[0] // 2)
        return -sum(pq)

Continue Practicing

#1792 maximum average pass ratio #2208 minimum operations to halve array sum #1705 maximum number of eaten apples