1046.Last_Stone_Weight(Easy).md

1046. Last Stone Weight (Easy)

Date and Time: Aug 28, 2024, 15:45 (EST)

Link: https://leetcode.com/problems/last-stone-weight/

Question:

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and

• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input: stones = [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 the last stone.

Example 2:

Input: stones = [1]

Output: 1

Constraints:

• 1 <= stones.length <= 30

• 1 <= stones[i] <= 1000

Walk-through:

1. Check the base case, if len(stones) == 1, we can just return the value stones[0].

2. We heapify all the stones into maxHeap, and store it with -i for i in stones, so we can have a maxHeap, which have the maximum value on top of the heap. Later, we just pop off the first two elements x, y from the maxHeap, and nagate those values to have the positive numbers back. If the difference between x, y is not 0, we heappush the difference into the heap. Otherwise, we don't add anything.

3. Check if len(maxHeap) == 1 in the end, if so, we return the value in maxHeap. Otherwise, we should return 0.

Python Solution:

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Base Case
        if len(stones) == 1:
            return stones[0]

        maxHeap = []
        for i in stones:
            heapq.heappush(maxHeap, -i)
        
        while len(maxHeap) > 1:
            x, y = -heapq.heappop(maxHeap), -heapq.heappop(maxHeap)
            if x != y:
                heapq.heappush(maxHeap, -abs(x-y))
        return -maxHeap[0] if len(maxHeap) == 1 else 0

Time Complexity: $O(n)$, n is the length of stones.
Space Complexity: $O(n)$

Java Solution:

In Java, we use PriorityQueue to implement minHeap and maxHeap. By default, the PriorityQueue<>() is a minHeap, so we use Collections.reverseOrder() to make the heap to be maxHeap.

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int i: stones)
            maxHeap.add(i);

        while (maxHeap.size() > 1) {
            int x = maxHeap.poll();
            int y = maxHeap.poll();
            if (x - y != 0) {
                maxHeap.add(Math.abs(x-y));
            }
        }
        
        if (maxHeap.size() == 1) {
            return maxHeap.poll();
        } else {
            return 0;
        }
    }
}

C++ Solution:

We can also use priority_queue<> in C++ to implement maxHeap or minHeap. By default, this is a maxHeap, we can add priority_queue<int, vector<int>, greater<int>> to make the pq to be minHeap. pq.top() returns reference to the top element.

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> maxHeap(stones.begin(), stones.end());
        while (maxHeap.size() > 1) {
            int x = maxHeap.top();
            maxHeap.pop();
            int y = maxHeap.top();
            maxHeap.pop();

            if (x != y) {
                maxHeap.push(abs(x-y));
            }
        }
        return maxHeap.empty() ? 0 : maxHeap.top();
    }
};

Runtime and Memory comparison

Language	Runtime	Memory
Python3	37 ms	16.5 MB
Java	1 ms	41.3 MB
C++	4 ms	9.6 MB