Lets Code Them Up!

Last Stone Weight

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

Example 1

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note:

  1. 1 <= stones.length <= 30
  2. 1 <= stones[i] <= 1000

Solution

The problem statement itself states that at each iteration we need to pick out the max two elements. So we need some sort of sorting to always get the max two elements.

We can use the heap data structure to maintain a sorted state of elements and always pick out the max two. The algorithm would be like this.

  1. Add all the elements of the array to the max heap.
  2. Loop until heap size is greater than equal to two
    1. Take out the max two elements x, y;
    2. if they are not equal, insert  x – y back into the heap. 
  3. return 0 if the heap is empty, else return the top element of the heap.

The time complexity is O(n log n) and space complexity is O(n) where n is the size of the array.

 

class Solution {
    public int lastStoneWeight(int[] stones) {
        
        //Initialize Priority Queue to Max Heap
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        
        //add all elements of stones array to priority queue
        for(int stone: stones){
            pq.add(stone);
        }
        
        //Loop until the heap has atleast two elements.
        while(pq.size() >= 2){
            
            //Pop out the two max elements
            int x = pq.poll();
            int y = pq.poll();
            
            //Push the difference between the two values back into the queue
            if(x != y){
                pq.add(x - y);
            }
        }
        
        // return 0 is queue is empty, else the top element
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

Source – LeetCode

Code – LastStoneWeight.java

 

Megha

,
,