How do you solve Last Stone Weight on LeetCode?

Last Stone Weight (LeetCode #1046) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Using a max-heap allows for efficient retrieval of the two heaviest stones.

What is the brute force solution for Last Stone Weight?

The brute force approach for Last Stone Weight is Brute Force, with O(n²) time complexity and O(1) space complexity. We can simulate the game by repeatedly finding the two heaviest stones, smashing them, and updating the list. This is straightforward but inefficient as it requires sorting or scanning the list multiple times. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Last Stone Weight?

Last Stone Weight uses the following concepts: Array, Heap (Priority Queue). The recommended patterns to study are: Heap (Priority Queue), Greedy Algorithms.

What are the interview tips for Last Stone Weight?

Always clarify the problem and constraints before jumping into coding. Discuss your thought process and approach with the interviewer. Consider edge cases and test your solution with them.

What are common mistakes when solving Last Stone Weight?

Not considering edge cases where there may be only one stone left. Forgetting to handle the case where two stones are equal and both are destroyed.

#1046

Last Stone Weight

Easy

ArrayHeap (Priority Queue)Heap (Priority Queue)Greedy Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

Using a max-heap (priority queue) allows us to efficiently retrieve and remove the two heaviest stones in logarithmic time, making the process much faster than sorting the entire array each time.

⚙️

Algorithm

4 steps

1Step 1: Create a max-heap from the stones array.
2Step 2: While there are at least two stones, extract the two heaviest stones.
3Step 3: Smash them together and, if there's a remaining weight, add it back to the heap.
4Step 4: Return the last remaining stone or 0 if no stones are left.

solution.py12 lines

1# Full working Python code
2import heapq
3
4def lastStoneWeight(stones):
5    stones = [-s for s in stones]  # Convert to max-heap
6    heapq.heapify(stones)
7    while len(stones) > 1:
8        x = -heapq.heappop(stones)
9        y = -heapq.heappop(stones)
10        if x != y:
11            heapq.heappush(stones, -(x - y))
12    return -stones[0] if stones else 0

ℹ

Complexity note: The time complexity is O(n log n) due to the heap operations (insert and extract) being logarithmic, and we perform these operations for each stone.

1Using a max-heap allows for efficient retrieval of the two heaviest stones.
2Simulating the game step-by-step helps in understanding the problem better.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.