LeetCode 1962 - Remove Stones to Minimize the Total

The problem gives us an array called piles, where each element represents the number of stones in a pile. We are also given an integer k, representing the exact number of operations we must perform. In one operation, we choose a pile and remove floor(pile / 2) stones from it.

leetcodemediumarraygreedyheap-(priority-queue)

LeetCode Problem 1962

Difficulty: 🟡 Medium
Topics: Array, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us an array called piles, where each element represents the number of stones in a pile. We are also given an integer k, representing the exact number of operations we must perform.

In one operation, we choose a pile and remove floor(pile / 2) stones from it. Since we remove half of the pile rounded down, the remaining pile becomes:

$$pile - \left\lfloor \frac{pile}{2} \right\rfloor$$

This is equivalent to:

$$\left\lceil \frac{pile}{2} \right\rceil$$

For example:

  • If a pile has 9 stones, we remove 4, leaving 5
  • If a pile has 6 stones, we remove 3, leaving 3
  • If a pile has 1 stone, we remove 0, so it stays 1

The goal is to minimize the total number of stones remaining after exactly k operations.

The important detail is that we may choose the same pile multiple times. This means we are free to repeatedly reduce the currently largest pile if that is beneficial.

The constraints are large:

  • Up to 10^5 piles
  • Up to 10^5 operations
  • Each pile may contain up to 10^4 stones

Because both n and k can be very large, any solution that repeatedly scans the entire array for the maximum value will likely be too slow.

Several edge cases are important:

  • A pile with value 1 never changes because floor(1 / 2) = 0
  • k may be larger than the number of piles, so we may revisit piles many times
  • The optimal choice at every step depends on the current largest pile, not the original largest pile
  • Multiple piles may have the same size

Understanding that we always want the greatest immediate reduction is the key insight that leads to the optimal greedy solution.

Approaches

Brute Force Approach

A straightforward approach is to simulate all k operations directly.

For each operation:

  1. Scan the entire array to find the largest pile
  2. Remove floor(pile / 2) stones from it
  3. Update the pile
  4. Repeat

This works because removing stones from the largest pile always gives the maximum immediate reduction. However, finding the largest pile by scanning the array costs O(n) time each operation.

Since we perform k operations, the total complexity becomes:

$$O(n \times k)$$

With both n and k potentially equal to 10^5, this could require up to 10^{10} operations, which is far too slow.

Optimal Approach, Greedy + Max Heap

The key observation is that at every step, the best move is always to reduce the current largest pile.

Suppose we have two piles:

  • Pile A = 20
  • Pile B = 8

Reducing pile A removes 10 stones, while reducing pile B removes only 4 stones. Choosing the larger pile always gives the greatest reduction in the total sum.

This greedy choice remains optimal after every operation because the only thing that matters is maximizing the reduction at the current step.

To efficiently retrieve the largest pile repeatedly, we use a max heap.

A heap allows us to:

  • Extract the largest pile in O(log n)
  • Insert the updated pile in O(log n)

This reduces the overall complexity dramatically.

Since Python's heapq is a min heap, we simulate a max heap by storing negative values.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(nk) O(1) Repeatedly scans entire array to find largest pile
Optimal O((n + k) log n) O(n) Uses max heap for efficient largest-element retrieval

Algorithm Walkthrough

  1. Compute the initial total number of stones.

Keeping track of the total lets us avoid summing the array again at the end. 2. Build a max heap containing all pile sizes.

Since Python only provides a min heap, we store negative values so the largest pile appears first. 3. Repeat the operation exactly k times.

In each iteration:

  • Remove the largest pile from the heap
  • Compute how many stones are removed:

$$removed = \left\lfloor \frac{largest}{2} \right\rfloor$$

  • Subtract removed from the running total
  • Compute the updated pile size:

$$newPile = largest - removed$$

  • Push the updated pile back into the heap
  1. After all operations are complete, return the total.

Why it works

The greedy strategy is optimal because each operation is independent in terms of maximizing reduction. Removing stones from the largest pile always removes at least as many stones as removing from any smaller pile.

The heap guarantees that we always choose the current largest pile efficiently. Since every operation makes the locally optimal choice and no future operation can compensate for wasting a reduction opportunity earlier, the algorithm produces the minimum possible total.

Python Solution

from typing import List
import heapq

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        total_stones = sum(piles)

        # Python heapq is a min heap, so use negative values
        max_heap = [-pile for pile in piles]
        heapq.heapify(max_heap)

        for _ in range(k):
            largest_pile = -heapq.heappop(max_heap)

            removed_stones = largest_pile // 2
            remaining_pile = largest_pile - removed_stones

            total_stones -= removed_stones

            heapq.heappush(max_heap, -remaining_pile)

        return total_stones

The implementation begins by computing the total number of stones across all piles. This allows the algorithm to update the answer incrementally rather than recalculating the sum repeatedly.

Next, the code constructs a max heap. Because Python's heapq module only supports min heaps, each pile is stored as a negative number. This trick causes the largest original pile to appear as the smallest negative value.

Inside the loop, the algorithm removes the largest pile, computes how many stones are removed, updates the total, and inserts the reduced pile back into the heap.

The heap always maintains the current state of the piles, ensuring that each operation selects the largest available pile efficiently.

Go Solution

package main

import (
	"container/heap"
)

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)

	item := old[n-1]
	*h = old[:n-1]

	return item
}

func minStoneSum(piles []int, k int) int {
	totalStones := 0

	h := &MaxHeap{}

	for _, pile := range piles {
		totalStones += pile
		*h = append(*h, pile)
	}

	heap.Init(h)

	for i := 0; i < k; i++ {
		largestPile := heap.Pop(h).(int)

		removedStones := largestPile / 2
		remainingPile := largestPile - removedStones

		totalStones -= removedStones

		heap.Push(h, remainingPile)
	}

	return totalStones
}

The Go implementation uses the container/heap package, which requires defining a custom heap type implementing the heap interface methods.

Unlike Python, Go allows us to directly define a max heap by customizing the Less function so that larger values have higher priority.

The rest of the logic mirrors the Python solution exactly.

Go integers are sufficient for this problem because the maximum possible total is:

$$10^5 \times 10^4 = 10^9$$

which fits safely inside a 32-bit signed integer.

Worked Examples

Example 1

Input:

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

Initial state:

Step Heap Content Largest Pile Removed New Pile Total
Start [9,5,4] - - - 18

Operation 1:

  • Extract 9
  • Remove 9 // 2 = 4
  • Remaining pile becomes 5
Step Heap Content Largest Pile Removed New Pile Total
After Op 1 [5,5,4] 9 4 5 14

Operation 2:

  • Extract 5
  • Remove 5 // 2 = 2
  • Remaining pile becomes 3
Step Heap Content Largest Pile Removed New Pile Total
After Op 2 [5,4,3] 5 2 3 12

Final answer:

12

Example 2

Input:

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

Initial total:

20

Initial heap:

[7,6,4,3]
Operation Largest Removed Remaining Total After
1 7 3 4 17
2 6 3 3 14
3 4 2 2 12

Final answer:

12

Complexity Analysis

Measure Complexity Explanation
Time O((n + k) log n) Heap construction costs O(n), each of the k operations performs heap pop and push
Space O(n) The heap stores all piles

Building the heap initially takes linear time. Each operation removes and reinserts one pile, and both heap operations cost O(log n).

Since we perform exactly k operations, the total running time becomes:

$$O(n + k \log n)$$

The heap stores all pile values, requiring O(n) additional memory.

Test Cases

from typing import List
import heapq

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        total_stones = sum(piles)

        max_heap = [-pile for pile in piles]
        heapq.heapify(max_heap)

        for _ in range(k):
            largest_pile = -heapq.heappop(max_heap)

            removed_stones = largest_pile // 2
            remaining_pile = largest_pile - removed_stones

            total_stones -= removed_stones

            heapq.heappush(max_heap, -remaining_pile)

        return total_stones

solution = Solution()

assert solution.minStoneSum([5, 4, 9], 2) == 12  # Example 1
assert solution.minStoneSum([4, 3, 6, 7], 3) == 12  # Example 2

assert solution.minStoneSum([1], 1) == 1  # Single pile that cannot shrink
assert solution.minStoneSum([10], 1) == 5  # Single operation on one pile
assert solution.minStoneSum([10], 2) == 3  # Repeated operations on same pile

assert solution.minStoneSum([10000], 100000) == 1  # Large k eventually stabilizes

assert solution.minStoneSum([2, 2, 2], 3) == 3  # Equal-sized piles
assert solution.minStoneSum([8, 1], 1) == 5  # Largest pile should be chosen
assert solution.minStoneSum([9, 8, 7], 0) == 24  # No operations

assert solution.minStoneSum([1, 1, 1, 1], 100) == 4  # All piles already minimal

assert solution.minStoneSum([20, 15, 10], 4) == 19  # Multiple greedy updates

Test Summary

Test Why
[5,4,9], k=2 Validates first official example
[4,3,6,7], k=3 Validates second official example
[1], k=1 Tests pile that cannot shrink
[10], k=1 Tests simple single reduction
[10], k=2 Tests repeated operations on same pile
[10000], k=100000 Tests very large k
[2,2,2], k=3 Tests equal-sized piles
[8,1], k=1 Ensures largest pile is selected
[9,8,7], k=0 Tests no operations
[1,1,1,1], k=100 Tests stable piles under many operations
[20,15,10], k=4 Tests repeated greedy heap updates

Edge Cases

One important edge case occurs when a pile contains only one stone. Since:

$$\left\lfloor \frac{1}{2} \right\rfloor = 0$$

the pile never changes. A buggy implementation might accidentally reduce it to zero or enter unnecessary processing loops. The heap-based solution handles this naturally because removing zero stones simply reinserts the value 1.

Another important case is when k is much larger than the number of piles. Since the same pile may be selected repeatedly, the algorithm must continue updating and reinserting piles correctly. The heap structure supports this naturally because every updated pile is pushed back for future consideration.

A third edge case involves multiple piles with identical sizes. The algorithm must still consistently choose one of the largest piles at each step. Since all equally large piles provide the same reduction amount, any tie-breaking order is valid. The heap implementation handles ties automatically without affecting correctness.

A final subtle edge case occurs when all piles become very small before operations finish. Eventually, every pile may become 1, after which no further reductions are possible. The algorithm still continues for the remaining operations, but each operation removes zero stones, leaving the total unchanged.