algoadvance

Leetcode 1046. Last Stone Weight

Problem Statement

LeetCode 1046 - Last Stone Weight

We are given a list of stones of various weights. In this problem, we will repeatedly smash the two heaviest stones together. Here are the rules:

  1. Select the two heaviest stones, say x and y.
  2. Smash them together.
    • If x == y, both stones are destroyed.
    • If x != y, the stone with weight x is destroyed, and the stone with weight y has new weight y - x.

Repeat this process until there is at most one stone left. Return the weight of the last remaining stone. If no stones are left, return 0.

Clarifying Questions

  1. Are the weights of the stones always positive integers?
    • Yes, the weights are positive integers.
  2. Is there a limit on the number of stones or their weights?
    • The number of stones (n) and their weights are within reasonable constraints for typical array operations in competitive programming.

Strategy

To solve this problem efficiently, we will utilize a max-heap data structure, which allows us to efficiently retrieve and remove the largest elements. Here’s the step-by-step plan:

  1. Insert all stones into a max-heap: In C++, we can use a priority queue with a custom comparator to simulate a max-heap.
  2. Simulate the smashing process:
    • Extract the two largest elements x and y (where x >= y).
    • If x != y, push the difference x - y back into the heap.
  3. Repeat the process until at most one stone remains in the heap.
  4. Return the weight of the last stone if there’s any, otherwise return 0.

Code

Here’s the implementation of the described strategy in C++:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

int lastStoneWeight(std::vector<int>& stones) {
    // Priority queue to act as a max-heap. 
    std::priority_queue<int> maxHeap(stones.begin(), stones.end());

    while (maxHeap.size() > 1) {
        int stone1 = maxHeap.top();
        maxHeap.pop();
        int stone2 = maxHeap.top();
        maxHeap.pop();
        
        if (stone1 != stone2) {
            maxHeap.push(stone1 - stone2);
        }
    }

    return maxHeap.empty() ? 0 : maxHeap.top();
}

int main() {
    std::vector<int> stones = {2, 7, 4, 1, 8, 1};
    std::cout << "The weight of the last remaining stone is: " << lastStoneWeight(stones) << std::endl;
    return 0;
}

Time Complexity

Overall, the time complexity is dominated by heap operations and is (O(n \log n)).

This solution efficiently handles the problem using a priority queue to always access the largest elements quickly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI