1962. Remove Stones to Minimize the Total

MediumArrayHeap (Priority Queue)
Leetcode Link

Problem Description

You are given an integer array called piles, where each element piles[i] indicates the number of stones in the i-th pile. You are also given an integer k. Your task is to perform exactly k operations on these piles, where in each operation you choose a pile and remove half of the stones in it (rounded down). The goal is to minimize the total number of stones left after all the operations have been performed.

In more detail, the operation consists of choosing any piles[i] and removing floor(piles[i] / 2) stones from it. It's important to note that the same pile can be chosen multiple times for successive operations.

After applying k operations, your function should return the minimum possible total number of stones remaining across all piles.

Intuition

The intuition behind the solution is to always target the pile with the largest number of stones for the reduction operation. This is because removing half from a larger number results in a bigger absolute reduction compared to removing half from a smaller pile. Over k operations, this strategy ensures the greatest possible reduction in the total number of stones.

To effectively apply this strategy, a max-heap is used. A max-heap is a binary tree structure where the parent node is always larger than or equal to the child nodes. This property allows for the efficient retrieval of the largest element in the collection, which is exactly what's needed to find the pile with the most stones.

In Python, the heapq library provides a min-heap, which can be turned into a max-heap by inserting negative values. Therefore, every value inserted into the heap is negated both when it's put in and when it's taken out.

Here's the step-by-step thought process:

  1. Negate all the elements in piles and store them in a heap to create a max-heap out of the Python min-heap implementation.
  2. For k iterations, remove the biggest element from the heap (which is the most negative), negate it to get the original value, and then remove half of it (as per the rules of the operation).
  3. Insert back the negated new value (after halving the biggest element) into the heap.
  4. After performing k operations, the heap will contain the negated values representing the remaining stones. To get the total, negate the sum of the heap's contents.

By always choosing the largest pile for halving, the algorithm ensures that the decrease in the total stone count is maximized with each operation.

Learn more about Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

Solution Approach

The solution leverages a max-heap data structure to efficiently track and remove the largest piles first. Here’s how the algorithm and data structures are utilized in the provided solution:

  1. A heap is created to maintain the current state of the piles. Since Python's heapq library implements a min-heap, the elements are negated before being pushed onto the heap to simulate a max-heap functionality.

  2. We iterate k times, each time performing the following steps:

    • The root of the heap (which in this case, is the maximum element, due to negation) is popped off the heap using heappop(). Since the elements are negated when stored in the heap, we negate it back to get the actual number of stones in the largest pile.
    • We then take the floor of halved value of this pile. The halving operation is conducted by adding 1 to the pile count and right-shifting (>> 1) by one, which in essence is dividing by two and using the floor value in integer division.
    • This new halved number of stones is negated and pushed back onto the heap to maintain the max-heap order. This is done using heappush().

    The code for this loop is as follows:

    1for _ in range(k):
2    p = -heappop(h)
3    heappush(h, -((p + 1) >> 1))

  3. Finally, after k iterations, the heap contains the negated counts of stones in each pile after the operations have been applied. To find the answer, we sum up all the elements in the heap (which involves negating them back to positive) and return this summed value as the total minimum possible number of stones remaining.

    This final step is summarized by this line of code:

    1return -sum(h)

This approach ensures that we are always working with the largest pile available after each operation, thus optimizing our strategy for minimizing the total number of stones.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the following piles and value of k:

  • piles = [10, 4, 2, 7]
  • k = 3

Now, let's walk through the solution step by step:

Initial State

  • First, we negate all the elements in piles to simulate a max-heap using Python's min-heap implementation: [-10, -4, -2, -7].

  • We use the heapq library to turn this into a heap: h = [-10, -4, -2, -7].

Operation 1

  • Since -10 is the maximum value (or smallest when considering negation), it is popped from the heap. We negate it to find the original amount of stones: 10.

  • Next, we remove half of the stones in this pile. Half of 10 is 5. Since we need to negate and re-insert into the heap, we insert -5.

  • Now the heap is [-7, -4, -2, -5].

Operation 2

  • The current maximum (minimum in our negated heap) is -7. We pop it and negate it: 7.

  • Removing half (rounded down) gives 7 / 2 which is 3 when rounded down. Negating and re-inserting -3, the heap is now [-5, -4, -2, -3].

Operation 3

  • The max value in our heap is now -5. We pop, negate, halve (rounding down to 2), and re-insert -2 into the heap.

  • The final state of the heap after 3 operations is [-4, -3, -2, -2].

Final Summation

  • To get the total number of stones remaining, we sum the negated values of the heap: -( -4 + -3 + -2 + -2 ).

  • This gives us 4 + 3 + 2 + 2 = 11 as the final answer.

So, after performing k = 3 operations on the piles, the minimum number of stones left is 11.

Solution Implementation

1from heapq import heappop, heappush
2
3class Solution:
4    def minStoneSum(self, piles, k):
5        # Initialize a max heap as Python only has a min heap implementation.
6        # We are inverting the values to simulate a max heap.
7        max_heap = []
8        for pile in piles:
9            # The minus sign ensures we create a max heap.
10            heappush(max_heap, -pile)
11      
12        # Perform 'k' operations to reduce the stones in the piles
13        for _ in range(k):
14            # Pop the largest pile and reduce its stones by half, rounded up.
15            largest_pile = -heappop(max_heap)
16            reduced_pile = (largest_pile + 1) >> 1  # Using bit shift to divide by 2
17          
18            # Push the reduced pile size back into the max heap.
19            heappush(max_heap, -reduced_pile)
20      
21        # The sum of the heap is negated to return the actual sum of pile sizes.
22        return -sum(max_heap)
23
1class Solution {
2    public int minStoneSum(int[] piles, int k) {
3        // Create a max-heap to store the piles in descending order
4        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
5      
6        // Add each pile to the max-heap
7        for (int pile : piles) {
8            maxHeap.offer(pile);
9        }
10      
11        // Perform the reduction operation k times
12        while (k-- > 0) {
13            // Retrieve and remove the largest pile from the heap
14            int largestPile = maxHeap.poll();
15            // Calculate the reduced number of stones and add back to the heap
16            maxHeap.offer((largestPile + 1) >> 1);
17        }
18      
19        // Calculate the total number of stones after k reductions
20        int totalStones = 0;
21        while (!maxHeap.isEmpty()) {
22            // Remove the stones from the heap and add them to the total count
23            totalStones += maxHeap.poll();
24        }
25      
26        // Return the total number of stones remaining after k operations
27        return totalStones;
28    }
29}
30
1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    int minStoneSum(vector<int>& piles, int k) {
7        // Create a max-heap to keep track of the stones in the piles
8        priority_queue<int> maxHeap;
9
10        // Populate the max-heap with the number of stones in each pile
11        for (int pile : piles) {
12            maxHeap.push(pile);
13        }
14
15        // Perform the operation k times
16        while (k-- > 0) {
17            // Retrieve the pile with the most stones
18            int largestPile = maxHeap.top();
19            maxHeap.pop();
20
21            // Remove half of the stones from the largest pile, round up if necessary
22            maxHeap.push((largestPile + 1) / 2);
23        }
24
25        // Calculate the remaining number of stones after k operations
26        int remainingStones = 0;
27        while (!maxHeap.empty()) {
28            remainingStones += maxHeap.top();
29            maxHeap.pop();
30        }
31
32        // Return the total number of remaining stones
33        return remainingStones;
34    }
35};
36
1// Import the necessary components for Heap
2import { Heap } from 'collections/heap.js'; // This library or similar would need to be imported for heap functionality.
3
4// Function signature in TypeScript with types defined
5function minStoneSum(piles: number[], k: number): number {
6    // Create a max-heap to keep track of the stones in the piles
7    let maxHeap = new Heap<number>(piles, null, (a: number, b: number) => b - a);
8
9    // Perform the operation 'k' times
10    for (let i = 0; i < k; i++) {
11        // Retrieve the pile with the most stones
12        let largestPile = maxHeap.pop(); // Assumes that Heap.pop retrieves the max element
13
14        // Remove half of the stones from the largest pile, round up if necessary
15        maxHeap.push(Math.ceil(largestPile / 2));
16    }
17
18    // Calculate the remaining number of stones after 'k' operations
19    let remainingStones = 0;
20    while (maxHeap.length > 0) {
21        remainingStones += maxHeap.pop();
22    }
23
24    // Return the total number of remaining stones
25    return remainingStones;
26}
27
28// Note that the `Heap` class I'm using above does not exist in default JavaScript/TypeScript and must be imported
29// from a library that provides heap data structure implementation. The example uses a fictional 'collections/heap.js'.
30// You'll need to find a suitable library with heap implementation, or you would have to implement your own 
31// heap structure to use this function as intended.
32
Not Sure What to Study? Take the 2-min Quiz：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by the following major operations:

  1. Converting the list piles into a heap: This operation is O(n) where n is the length of piles.
  2. The main loop which is executed k times:
    • The heap operation heappop: Each pop operation has a complexity of O(log n).
    • The update and heappush back into the heap: These have a complexity of O(log n) for each push operation.

Therefore, the overall time complexity of the loop is O(k * log n). Combining this with the heap conversion, the total time complexity is O(n + k * log n).

Space Complexity

The space complexity is determined by the space needed to store the heap. Since we are not using any additional data structures that grow with input size other than the heap, the space complexity is O(n), where n is the length of the list piles.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫