Watch 10 video solutions for Remove Stones to Minimize the Total, a medium level problem involving Array, Greedy, Heap (Priority Queue). This walkthrough by Coding Decoded has 890 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:
piles[i] and remove floor(piles[i] / 2) stones from it.Notice that you can apply the operation on the same pile more than once.
Return the minimum possible total number of stones remaining after applying the k operations.
floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).
Example 1:
Input: piles = [5,4,9], k = 2 Output: 12 Explanation: 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 Explanation: 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 <= 1051 <= piles[i] <= 1041 <= k <= 105Problem Overview: You are given an array of stone piles. In each of the k operations, choose a pile and remove floor(pile / 2) stones from it. The goal is to minimize the total number of stones remaining after exactly k operations.
Approach 1: Use a Max-Heap for Efficient Pile Reduction (O(n + k log n) time, O(n) space)
This problem is naturally solved with a greedy strategy: always reduce the largest pile because removing half from a bigger pile decreases the total more. Store all piles in a max-heap so you can quickly access the current largest pile. For each of the k operations, extract the maximum element, remove floor(pile / 2), then push the updated pile back into the heap. Heap extraction and insertion both cost O(log n), so the total runtime becomes O(n + k log n) including heap construction.
The key insight is that the largest pile always provides the greatest reduction in the sum. Using a heap (priority queue) guarantees that this choice is efficient at every step. This approach works well even when k is large because each operation only touches the heap root.
Approach 2: Simulate Heap with Sorting (O(k n log n) time, O(1) extra space)
If a priority queue is unavailable in the language environment, you can simulate the greedy strategy by repeatedly sorting the array. In each operation, sort the piles in descending order, reduce the first element by floor(pile / 2), then continue to the next iteration. Sorting ensures the largest pile is always selected.
This approach still follows the same greedy idea but is less efficient because the array is re-sorted every time. Each iteration costs O(n log n), leading to O(k n log n) overall time. It is mainly useful in environments where implementing a heap is inconvenient or when input sizes are small.
Recommended for interviews: Interviewers typically expect the max-heap solution. Recognizing that the optimal move is always reducing the largest pile shows good greedy intuition, and implementing it with a priority queue demonstrates familiarity with efficient data structures. The sorting simulation helps explain the greedy reasoning, but the heap approach shows stronger algorithmic optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Max-Heap (Priority Queue) | O(n + k log n) | O(n) | General case and interview settings where efficient repeated max selection is needed |
| Sorting Each Operation | O(k n log n) | O(1) | When heap libraries are unavailable or constraints are small |