Skip to main content
Talentd

Remove Stones to Minimize the Total - Solution & Explanation

MediumArrayGreedyHeap (Priority Queue)12 min readAsked at: Amazon, NVIDIA, Salesforce +2
Practice this problem

Problem Statement

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:

  • Choose any 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 <= 105
  • 1 <= piles[i] <= 104
  • 1 <= k <= 105

Approach Overview

Problem 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 1: Approach 1: Use a Max-Heap for Efficient Pile Reduction

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.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

Time Complexity: O(k log n) where n is the number of piles. Space Complexity: O(n) due to the heap storage.

Try this approach in the editor →

Approach 2: Approach 2: Simulate Heap with Sorting

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.

Code

CC#

C

C#

Complexity

Time Complexity: O(k n log n), Space Complexity: O(1) (in-place sort).

Try this approach in the editor →

Approach 3: 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.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 OperationO(k n log n)O(1)When heap libraries are unavailable or constraints are small

Video Solution

Remove Stones to Minimize the Total (Google, Miscrosoft, Netflix, Meta) : Explanation ➕ Live Coding • codestorywithMIK • 10,968 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Remove Stones to Minimize the Total easy or hard?
The problem is classified as Medium difficulty. The main challenge is recognizing the greedy insight that the largest pile should always be reduced first and implementing it efficiently with a heap.
Remove Stones to Minimize the Total Python/Java solution
Python implementations typically use heapq with negative values to simulate a max-heap, while Java uses PriorityQueue with a reverse comparator. Both versions repeatedly pop the largest pile, reduce it by floor(pile/2), and push the updated pile back until k operations are completed.
What is the best approach for Remove Stones to Minimize the Total?
The most efficient approach uses a max-heap (priority queue). Always remove stones from the largest pile because it produces the biggest reduction in total stones. Extract the maximum pile, remove floor(pile/2), and push the updated value back into the heap. This greedy method runs in O(n + k log n) time with O(n) space.
How to solve Remove Stones to Minimize the Total in O(n + k log n)?
Insert all pile sizes into a max-heap. Repeat k times: remove the largest pile, compute floor(pile/2), subtract it from the pile, and push the updated value back into the heap. After all operations, sum the heap values to get the remaining stones. Each operation uses O(log n) heap operations.
Is Remove Stones to Minimize the Total asked at Google/Amazon/Meta?
This problem represents a common greedy + heap pattern frequently seen in interviews at companies like Amazon, Google, and Meta. Variants involving repeatedly selecting the largest element using a priority queue appear in many real interview questions.
What data structure is used in Remove Stones to Minimize the Total?
A max-heap (priority queue) is the key data structure. It allows efficient retrieval and update of the largest pile in O(log n) time. The problem combines heap operations with a greedy strategy to minimize the total stones.
What is the time complexity of Remove Stones to Minimize the Total?
The optimal heap-based solution runs in O(n + k log n) time. Building the max-heap takes O(n), and each of the k operations performs a heap extraction and insertion costing O(log n). Space complexity is O(n) for storing the heap.

Ready to solve this problem?

Practice Remove Stones to Minimize the Total with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximal Score After Applying K Operations

Next

Minimum Operations to Halve Array Sum