Log inSign up
easyLeetCodeNot Started

Last Stone Weight

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

On each turn, choose the two heaviest stones x and y (x <= y) and smash them together: - If x == y, both stones are destroyed. - If x != y, stone of weight x is destroyed, and the stone of weight y has new weight y - x.

Return the weight of the last remaining stone, or 0 if no stones remain.

Example 1 · Example 1: Six Stones:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 1. Combine 7 and 8 -> 8 - 7 = 1. Stones left: [2, 4, 1, 1, 1]. 2. Combine 2 and 4 -> 4 - 2 = 2. Stones left: [2, 1, 1, 1]. 3. Combine 2 and 1 -> 2 - 1 = 1. Stones left: [1, 1, 1]. 4. Combine 1 and 1 -> 0. Stones left: [1]. Last stone weight is 1. Max-Heap (Start): (8) / \ (7) (4) / \ / (1) (2) (1)

Example 2 · Example 2: Single Stone:

Input: stones = [1]
Output: 1
Explanation: Only 1 stone exists; weight is 1.

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement dynamic maximum extraction using a Max-Heap.
  • Handle simulation termination and empty heap edge cases.
  • Compare full-sort simulation vs priority queue simulation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Repeatedly select top two maximum values and replace with their difference.
  • Simulation until size <= 1.
  • Max-Heap simulation pattern.

Algorithmic Decision Tree:

  • Sorting every round takes O(N2 log N).
  • Max-Heap allows dynamic extraction and re-insertion in O(log N) per turn.

Connected Patterns:

Minimum Cost to Connect SticksKth Largest Element in an Array

1. Brute Force — Sort Array on Every Smash

Intuition

Keep array sorted ascending. While length > 1, remove the last two elements. If they differ, append the difference and re-sort. Return last element or 0.

When to apply: When stones array is tiny (N <= 30) and no heap is available.

Algorithm

  1. Step 1: While array size > 1:
  2. Step 2: Sort array ascending.
  3. Step 3: Pop last two elements y and x.
  4. Step 4: If y != x, append y - x.
  5. Step 5: Return array[0] if size == 1, else 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int lastStoneWeight(vector<int>& stones) {
9 while (stones.size() > 1) {
10 sort(stones.begin(), stones.end());
11 int y = stones.back(); stones.pop_back();
12 int x = stones.back(); stones.pop_back();
13 if (y != x) {
14 stones.push_back(y - x);
15 }
16 }
17 return stones.empty() ? 0 : stones[0];
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> stones = {2, 7, 4, 1, 8, 1};
24 cout << "Last Stone Weight (Brute Force): " << sol.lastStoneWeight(stones) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N^2 log N) — O(N2 log N) repeated sorting.
  • Space complexity: O(N) — O(N) storage.

Why Brute Force Doesn't Scale:

With N = 105, repeated sorting takes ~1010 operations. Max-Heap takes ~1.7 * 106 operations.

Max-Heap takes ~1ms for standard arrays.

2. Better — Linear Scan Simulation

Intuition

Loop while more than 1 stone remains. Find the index of the maximum, remove it, then find the index of the second maximum, remove it, and append the positive difference.

When to apply: When memory is tight and heap libraries are unavailable.

Algorithm

  1. Step 1: Loop while array size > 1.
  2. Step 2: Linear scan to find and remove max1.
  3. Step 3: Linear scan to find and remove max2.
  4. Step 4: If max1 != max2, append max1 - max2.
  5. Step 5: Return last stone or 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int lastStoneWeight(vector<int>& stones) {
9 while (stones.size() > 1) {
10 auto it1 = max_element(stones.begin(), stones.end());
11 int y = *it1;
12 stones.erase(it1);
13
14 auto it2 = max_element(stones.begin(), stones.end());
15 int x = *it2;
16 stones.erase(it2);
17
18 if (y != x) {
19 stones.push_back(y - x);
20 }
21 }
22 return stones.empty() ? 0 : stones[0];
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> stones = {2, 7, 4, 1, 8, 1};
29 cout << "Last Stone Weight (Linear Scan): " << sol.lastStoneWeight(stones) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2) — O(N2) linear scans per turn.
  • Space complexity: O(N) — O(N) storage.

3. Optimal — Max-Heap Simulation

Intuition

Build a Max-Heap in O(N). In each turn, extract top two stones y and x. If y > x, push y - x back into the heap. Repeat until heap size is 0 or 1. Return top or 0.

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: Insert all stones into a Max-Heap.
  2. Step 2: While heap.size() > 1:
  3. Step 3: y = heap.pop(), x = heap.pop().
  4. Step 4: If y > x, heap.push(y - x).
  5. Step 5: Return heap.empty() ? 0 : heap.top().

Interactive Trace for Last Stone Weight

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Heap built with [8, 7, 4, 1, 2, 1]
Visual state
Values and pointers at this exact step
tree
Root: 8
8
Child: 7
7
Child: 4
4

Node order shown; add connections to display explicit tree edges.

smash: s1
Check / comparison
8 - 7 = 1 > 0.
Decision / next transition
Pop 8 and 7, push 1. Heap size becomes 5.
Why this step matters

Step 1: Heap built with [8, 7, 4, 1, 2, 1]. Top stones are y=8 and x=7.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6class Solution {
7public:
8 int lastStoneWeight(vector<int>& stones) {
9 priority_queue<int> maxHeap(stones.begin(), stones.end());
10
11 while (maxHeap.size() > 1) {
12 int y = maxHeap.top(); maxHeap.pop();
13 int x = maxHeap.top(); maxHeap.pop();
14
15 if (y != x) {
16 maxHeap.push(y - x);
17 }
18 }
19 return maxHeap.empty() ? 0 : maxHeap.top();
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> stones = {2, 7, 4, 1, 8, 1};
26 cout << "Last Stone Weight (Optimal Max-Heap): " << sol.lastStoneWeight(stones) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) across at most N turns.
  • Space complexity: O(N) — O(N) heap memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Sort Array Every TurnO(N^2 log N)O(1) auxiliarySort array ascending, pop last two elements, if different push difference, repeat.Repeated full sorts.
2.Better — Linear Scan for Two MaximaO(N^2)O(1) auxiliaryFind indices of two largest elements via linear scan, smash and overwrite.Linear scans.
3.Optimal — Max-Heap SimulationOptimalO(N log N)O(N)Heapify stones into Max-Heap. While size > 1, pop y and x, push y - x if positive.None. Optimal.

Common Pitfalls & Crucial Edge Cases

Calling heap.top() on empty heap

When all stones destroy each other, heap is empty; must guard with empty check and return 0.

Min-Heap instead of Max-Heap

Problem requires smashing the two *heaviest* stones, which needs a Max-Heap.

Pushing zero when x == y

Zero stones are completely destroyed; do not push 0 into heap.

Crucial Edge Cases to Validate:

  • Single stone (N = 1) — Returns that stone's weight directly.
  • Two identical stones (N = 2) — Both destroyed; returns 0.
  • All stones destroyed — Heap is empty; returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the clean Max-Heap condition while heap.size() > 1.
  2. Remember to handle the empty heap return condition (return 0).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the game terminate in at most N turns?

Back to DSA Sheet