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.
The key idea of this approach is to use a max-heap (priority queue) to efficiently extract and update the largest pile each time. We repeatedly apply the operation on the largest pile, reducing it by floor(piles[i] / 2). Each time we remove the stones, we push the updated pile back into the max-heap for further operations until k operations are completed.
This Python solution uses the heapq library to maintain a max-heap (implemented as a min-heap with negative values). It performs k operations, each time reducing the largest pile. The final step returns the sum of the remaining piles.
Python
Java
JavaScript
Time Complexity: O(k log n) where n is the number of piles. Space Complexity: O(n) due to the heap storage.
This approach involves using sorting to simulate the operations of a max-heap. The array of piles is repeatedly sorted to find the largest pile, then the operation is applied, and the sequence is repeated for k times.
This C solution uses qsort to sort the piles array in descending order in each iteration to simulate the max-heap top extraction. The largest element is reduced, and the process repeats for k times. Finally, it returns the sum of the left piles.
Time Complexity: O(k n log n), Space Complexity: O(1) (in-place sort).
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.
We create a priority queue (max heap) pq to store the number of stones in each pile. Initially, we add the number of stones in all piles to the priority queue.
Next, we perform k operations. In each operation, we take out the top element x of the priority queue, halve x, and then add it back to the priority queue.
After performing k operations, the sum of all elements in the priority queue is the answer.
The time complexity is O(n + k times log n), and the space complexity is O(n). Where n is the length of the array piles.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Use a Max-Heap for Efficient Pile Reduction | Time Complexity: O(k log n) where n is the number of piles. Space Complexity: O(n) due to the heap storage. |
| Approach 2: Simulate Heap with Sorting | Time Complexity: O(k n log n), Space Complexity: O(1) (in-place sort). |
| Greedy + Priority Queue (Max Heap) | — |
| 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 |
`Leetcode 1962 Remove Stones to Minimize the Total | Coding Decoded SDE Sheet • Coding Decoded • 890 views views
Watch 9 more video solutions →Practice Remove Stones to Minimize the Total with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor