An integer array stones contains positive stone weights. During every turn, select the two heaviest stones with weights x and y, where x <= y.
Equal weights destroy both stones. Different weights destroy the lighter stone and replace the heavier stone with weight y - x. Continue until at most one stone remains. Return the final stone weight, or return 0 when no stone remains.
Example 1
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
Explanation: Collisions use pairs (8, 7), (4, 2), (2, 1), and (1, 1). The corresponding remainders are 1, 2, 1, and 0, leaving one stone of weight 1.
Example 2
Input: stones = [3, 3]
Output: 0
Explanation: Equal weights destroy both stones, so no stone remains.
Brute Force Approach
The collision rule always needs the two greatest current weights. Sorting the active weights places the required pair at the end, making each collision easy to simulate. A positive difference returns to the collection and participates in a later round.
The same ordering work starts again after every collision because a new difference can belong anywhere in sorted order. Repeated sorting keeps the method simple, although earlier comparisons are discarded and performed again.
Algorithm
Begin with a copy of
stones, preserving the supplied array while all collisions change only the working collection.Keep processing while at least two weights remain because every legal collision requires the two heaviest available stones.
Sort the working collection in ascending order, so the heaviest and second-heaviest stones occupy the final two positions.
Remove the heaviest stone first and the second-heaviest stone next, preserving non-negative subtraction order for the collision result.
Compare the removed weights and insert
heaviest - secondHeaviestonly for unequal weights, so equal weights disappear without creating a zero-weight stone.Repeat sorting after every insertion because the new difference can occupy any position among the remaining weights.
Return
0for an empty collection or return the sole remaining weight, so both possible finishing states map to the required answer.
Dry Run
Last stone Weight
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Simulates collisions by sorting before every round. int lastStoneWeight(vector<int>& stones) { // Preserve the supplied weights in a working copy. vector<int> working = stones; // Continue while a collision pair remains available. while (working.size() > 1) { // Place the two heaviest weights at the end. sort(working.begin(), working.end()); // Remove the heaviest available stone. int heaviest = working.back(); working.pop_back(); // Remove the second-heaviest available stone. int secondHeaviest = working.back(); working.pop_back(); // Unequal stones leave a positive difference. if (heaviest != secondHeaviest) { // Return the surviving weight to the collection. working.push_back(heaviest - secondHeaviest); } } // An empty collection represents complete destruction. if (working.empty()) { return 0; } // The sole remaining weight is the final answer. return working[0]; }};// Driver codeint main() { vector<int> stones = {2, 7, 4, 1, 8, 1}; Solution obj; cout << obj.lastStoneWeight(stones) << endl; return 0;}Complexity Analysis
Time Complexity: O(N2 log N), where N is the number of stones, because at most N - 1 rounds sort up to N active weights, making repeated sorting the dominant cost.
Space Complexity: O(N), because the working collection stores at most N stone weights, while the remaining variables use only lower-order extra space.
Optimal Approach
Repeated sorting performs more ordering work than each collision needs. A max heap keeps the greatest current weight at the top and restores only the affected path after a removal or insertion. Two removals therefore expose the exact pair required by the rules.
A positive collision difference returns through one heap insertion, automatically finding a valid priority position. Equal weights need no insertion. The heap shrinks after every round and leaves either one maximum or an empty structure.
Algorithm
Begin with a max heap containing every stone weight, making the greatest active weight available at the root throughout the simulation.
Keep processing while the heap contains at least two weights because every collision consumes exactly one heaviest pair.
Remove the heap maximum as
heaviest, so the greatest current weight becomes available without a full sort.Remove the next heap maximum as
secondHeaviest, so the only remaining weight eligible for the collision becomes available.Compare both weights and insert
heaviest - secondHeaviestonly for unequal values, so equal values vanish without a heap insertion.Let heap restoration place every inserted difference correctly, preserving fast access to the next heaviest pair.
Return
0for an empty heap or return the root weight, so both valid ending states map to the required answer.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Simulates collisions with a max-priority queue. int lastStoneWeight(vector<int>& stones) { // Build a max heap containing every stone weight. priority_queue<int> maxHeap; // Insert every weight for greatest-first removal. for (int stone : stones) { maxHeap.push(stone); } // Continue while a collision pair remains available. while (maxHeap.size() > 1) { // Remove the heaviest available stone. int heaviest = maxHeap.top(); maxHeap.pop(); // Remove the second-heaviest available stone. int secondHeaviest = maxHeap.top(); maxHeap.pop(); // Unequal stones leave a positive difference. if (heaviest != secondHeaviest) { // Restore the surviving weight to heap order. maxHeap.push(heaviest - secondHeaviest); } } // An empty heap represents complete destruction. if (maxHeap.empty()) { return 0; } // The remaining maximum is the final answer. return maxHeap.top(); }};// Driver codeint main() { vector<int> stones = {2, 7, 4, 1, 8, 1}; Solution obj; cout << obj.lastStoneWeight(stones) << endl; return 0;}Complexity Analysis
Time Complexity: O(N log N), where N is the number of stones, because at most N - 1 rounds perform a constant number of heap removals and insertions, each taking O(log N) time.
Space Complexity: O(N), because the max-heap stores at most N stone weights, while the remaining variables use constant extra space.
Interview follow-up Questions
The game rules explicitly select the two greatest current weights. Choosing any lighter stone changes later collisions and can produce a different final weight.
Be the first to add a comment.