We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Last Stone Weight

Number: 1127

Difficulty: Easy

Paid? No

Companies: Nvidia, Amazon, Microsoft, Meta, Google, Salesforce, Flipkart, Rippling, PayPal, Uber, Agoda, Roku, Oracle

Problem Description

We are given an array of stone weights. On each turn, we pick the two heaviest stones and smash them together. If the stones have equal weights, both are destroyed. If they are different, the lighter stone is completely destroyed and the heavier stone is reduced by the weight of the lighter. The process continues until at most one stone remains. The task is to return the weight of the remaining stone, or 0 if no stone is left.

Key Insights

  • Use a max-heap (or simulate one) to always access the two largest stones quickly.
  • If the two stones are equal, both are removed; otherwise, the difference is pushed back into the heap.
  • Continue the process until the heap has one or no stone left.
  • For languages without a max-heap in their standard library (e.g., Python), simulate one by pushing negative values.

Space and Time Complexity

Time Complexity: O(n log n) – Each stone removal and insertion takes O(log n) and in the worst-case scenario, we perform O(n) operations. Space Complexity: O(n) – The heap stores all the stones initially.

Solution

We solve the problem by using a priority queue (max-heap). In Python, we simulate a max-heap by inserting the negative of each stone's weight into a min-heap. In JavaScript, due to the lack of a built-in heap structure, we sort the array in descending order at each iteration (acceptable given the small constraints). In C++ and Java, we use the standard priority_queue. The algorithm repeatedly extracts the two largest stones, computes their difference, and if the difference is non-zero, it is inserted back into the heap. This process repeats until there is at most one stone left.

Code Solutions

import heapq

def lastStoneWeight(stones):
    # Create a max heap by inserting negative values of stones
    max_heap = [-stone for stone in stones]
    heapq.heapify(max_heap)
    
    # While more than one stone remains
    while len(max_heap) > 1:
        # Get the heaviest stone (largest value, but stored as negative)
        heaviest = -heapq.heappop(max_heap)
        # Get the next heaviest stone
        next_heaviest = -heapq.heappop(max_heap)
        
        # If the stones are not equal, push the difference back into the heap
        if heaviest != next_heaviest:
            diff = heaviest - next_heaviest
            heapq.heappush(max_heap, -diff)
    
    # If there is a stone left, return its weight. Otherwise, return 0.
    return -max_heap[0] if max_heap else 0

# Example usage:
# print(lastStoneWeight([2,7,4,1,8,1]))
← Back to All Questions