1046. Last Stone Weight

📝 Problem Details

• Title: 1046. Last Stone Weight
• Link: https://leetcode.com/problems/last-stone-weight/
• Difficulty: Easy
• Tags/Categories: Priority-Queue

💭What Were My Initial Thoughts?

have a priority queue that stores elements from greatest -> lowest
pop the front two elements from the queue
conduct the "smashing" of the stones and reinsert the new value into the queue
break out of the loop when there is a single element remaining and return it 

🤔What Did I Struggle With?

~

💡 Explanation of Solution

same as initial thoughts

⌛ Complexity Analysis

Time Complexity: O(n log n) for the sorting associated with priority queue heapify
Space Complexity: O(n) for storage of elements in the priority queue

💻 Implementation of Solution

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for (int stone : stones) {
            pq.push(stone);
        }
        while (pq.size() > 1) {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
 
            if (x != y) pq.push(x - y);
        }
 
        return pq.empty() ? 0 : pq.top();
    }
};