1962. Remove Stones to Minimize the Total

Hello, reader 👋🏽 ! Welcome to day 88 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1962. Remove Stones to Minimize the Total.

🤔 Problem Statement

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the i<sup>th</sup> 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.
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.
E.g.:
- piles = [5,4,9], k = 2 => 12
- piles = [4,3,6,7], k = 3 => 12

💬 Thought Process - Greedy

This is a greedy problem where we have to return the minimum number of stones left after applying k operations.
The greediest way to reduce the number of stones is to apply the k operations on piles that have the greatest number of stones.
Let's understand with this example: piles = [5,4,9], k = 12
- Now the pile with the largest number of stones is piles[2] = 9. Hence, the first operation can be applied on this.
  - Now, pile = 9. We have to remove 9/2 = 4 rocks from it. Hence, pile = pile - 4 => pile = 5
- The next largest pile has 5 stones. Let's assume it's going to be pile[0]. Hence, the second operation can be applied on this:
  - pile = 5. We have to remove 5/2 = 2 rocks from it. Hence, pile = pile - 2 => pile = 3
- After k = 2 operations, piles looks like this: [3,4,5]. Total is: 3+4+5 = 12.
Now the question is how do we find the largest pile every after every operation?
We of course cannot keep sorting after every operation. That would take O(k * n log n) and that is not efficient.
We can leverage any data structure that keeps track of the largest value from a list -> priority queue/ heap.
For every operation, we can poll the first element, apply the operation and reduce the stones and then add it back to the queue.
If we maintain a max heap, during every operation we can access the pile with the maximum value.

👩🏽‍💻 Solution - Greedy

class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(
            (a,b) -> b-a
        );

        for(int pile: piles) {
            pq.add(pile);
        }

        while(k-- > 0) {
            int pile = pq.remove();
            int half = pile / 2; 
            pile -= half;
            pq.add(pile);
        }

        int total = 0;
        while(!pq.isEmpty()) {
            total += pq.poll();
        }

        return total;
    }
}

Time Complexity: O(n + k*log n)
    - n: building a heap of n elements
    - k*log n: performing k operations on a heap with n elements
Space Complexity: O(n)
    - Maintain a heap

You can find the link to all the solutions on GitHub for this question here: 2279. Maximum Bags With Full Capacity of Rocks.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian