Solved problem 1046 : Last Stone Weight

racoelhosilva · racoelhosilva · commit b21a942568c3 · 2023-12-19T10:06:55.000Z
diff --git a/Priority Queue/Easy/1046_LastStoneWeight.cpp b/Priority Queue/Easy/1046_LastStoneWeight.cpp
@@ -0,0 +1,42 @@
+/* 
+ * Problem: 1046 
+ * Name: Last Stone Weight
+ * Difficulty: Easy
+ * Topic: Priority Queue
+ * Link: https://leetcode.com/problems/last-stone-weight/
+ */
+ 
+#include <bits/stdc++.h>
+using namespace std;
+
+//      Naive Approach
+// Time Complexity: O(n log n)
+// Space Complexity: O(1)
+int lastStoneWeightNaive(vector<int>& stones) {
+    while (stones.size() > 1){
+        sort(stones.begin(), stones.end());
+        int largest = stones[stones.size()-1];
+        int secondLargest = stones[stones.size()-2];
+        stones.pop_back();
+        if (largest == secondLargest){
+            stones.pop_back();
+        }
+        else {
+            stones[stones.size()-1] = largest-secondLargest;
+        }
+    }
+    return stones.empty() ? 0 : stones[0];
+}
+
+//      Priority Queue
+// Time Complexity: O(n)
+// Space Complexity: O(n)
+int lastStoneWeightPQ(vector<int>& stones) {
+    priority_queue<int> remainingStones(stones.begin(), stones.end());
+    while (remainingStones.size() > 1){
+        int largest = remainingStones.top(); remainingStones.pop();
+        int secondLargest = remainingStones.top(); remainingStones.pop();
+        remainingStones.push(largest - secondLargest);
+    }
+    return remainingStones.top();
+}
diff --git a/README.md b/README.md
@@ -16,7 +16,7 @@
 
 ### Problems Solved
 
-| Total | 42 |
+| Total | 43 |
 |:---:|:---:|
 
 #### Search By Topic
@@ -36,7 +36,7 @@
 | Intervals | 1 |
 | Linked Lists | 5 |
 | Math & Geometry | 2 |
-| Priority Queue | 1 |
+| Priority Queue | 2 |
 | Sliding Window | 1 |
 | Stack | 2 |
 | Tries | 0 |
@@ -46,7 +46,7 @@
 
 | Difficulty | Number |
 |:---|---:|
-| Easy | 41 |
+| Easy | 42 |
 | Medium | 1 |
 | Hard | 0 |
 
