Skip to main content
CodePeetCodePeet
CodePeet 250

Last Stone Weight

EASYProblemSolveExternal Links

Description

You have a collection of stones, each with a positive integer weight. On each turn you pick the two heaviest stones and smash them together according to these rules:

  • If the two stones have equal weight, both stones are completely destroyed.
  • If the two stones have different weights, the lighter stone is destroyed and the heavier stone's weight is reduced by the lighter stone's weight (the remaining piece goes back into the collection).

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

Examples

Example 1

Input: stones = [2, 7, 4, 1, 8, 1]

Output: 1

Explanation:

  • Smash 8 and 7 → 8 - 7 = 1 remains → stones become [2, 4, 1, 1, 1]
  • Smash 4 and 2 → 4 - 2 = 2 remains → stones become [2, 1, 1, 1]
  • Smash 2 and 1 → 2 - 1 = 1 remains → stones become [1, 1, 1]
  • Smash 1 and 1 → equal, both destroyed → stones become [1]

One stone remains with weight 1.

Example 2

Input: stones = [1]

Output: 1

Explanation: There is only one stone, so no smashing occurs. Return its weight directly.

Constraints

  • 1 ≤ stones.length ≤ 30
  • 1 ≤ stones[i] ≤ 1000

Editorial

Brute Force - Sort and Pick

Intuition

The problem tells us to repeatedly pick the two heaviest stones. The most natural way to find the two heaviest is to simply sort the collection after every turn.

Once sorted in ascending order, the two heaviest stones are always the last two elements. We remove them, compute the result of smashing, and if the result is non-zero we put the remaining piece back into the collection. Then we sort again and repeat.

Think of it like arranging a line of people by height. Each round you pull the two tallest out of the line, let them do something, and if one remains you put them back. Then you rearrange the entire line by height again.

This is simple and correct, but the repeated sorting is doing more work than necessary. We will see later how a smarter data structure can avoid re-sorting from scratch every turn.

Step-by-Step Explanation

Let's trace through stones = [2, 7, 4, 1, 8, 1]:

Step 1: Sort the array → [1, 1, 2, 4, 7, 8]. The two heaviest are 8 and 7 (last two elements).

Step 2: Smash 8 and 7. They are not equal: 8 - 7 = 1. Remove both, put 1 back. Array becomes [1, 1, 1, 2, 4].

Step 3: Sort again → [1, 1, 1, 2, 4]. The two heaviest are 4 and 2.

Step 4: Smash 4 and 2. Not equal: 4 - 2 = 2. Remove both, put 2 back. Array becomes [1, 1, 1, 2].

Step 5: Already sorted. The two heaviest are 2 and 1.

Step 6: Smash 2 and 1. Not equal: 2 - 1 = 1. Remove both, put 1 back. Array becomes [1, 1, 1].

Step 7: Already sorted. The two heaviest are 1 and 1.

Step 8: Smash 1 and 1. Equal — both destroyed. Remove both. Array becomes [1].

Step 9: Only one stone remains. Return 1.

Brute Force — Sort, Pick Two Heaviest, Smash, Repeat — Watch how the array is sorted from scratch each round so the two heaviest stones appear at the end, then one round of smashing occurs before the next sort.

Algorithm

  1. While the number of stones is greater than 1:
    a. Sort the stones array in ascending order
    b. Remove the last element (heaviest, call it y)
    c. Remove the new last element (second heaviest, call it x)
    d. If x ≠ y, append y - x back into the array
  2. If the array is empty, return 0
  3. Otherwise return the single remaining element

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        while (stones.size() > 1) {
            sort(stones.begin(), stones.end());
            int y = stones.back(); stones.pop_back();
            int x = stones.back(); stones.pop_back();
            if (x != y) {
                stones.push_back(y - x);
            }
        }
        return stones.empty() ? 0 : stones[0];
    }
};
class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        while len(stones) > 1:
            stones.sort()
            y = stones.pop()
            x = stones.pop()
            if x != y:
                stones.append(y - x)
        return stones[0] if stones else 0
import java.util.*;

class Solution {
    public int lastStoneWeight(int[] stones) {
        List<Integer> list = new ArrayList<>();
        for (int s : stones) list.add(s);

        while (list.size() > 1) {
            Collections.sort(list);
            int y = list.remove(list.size() - 1);
            int x = list.remove(list.size() - 1);
            if (x != y) {
                list.add(y - x);
            }
        }

        return list.isEmpty() ? 0 : list.get(0);
    }
}

Complexity Analysis

Time Complexity: O(n² log n)

Each round we sort the remaining stones, which costs O(k log k) where k is the current count. Each round removes at least one stone (two if they are equal), so there are at most n - 1 rounds. In the worst case every round removes exactly one stone, giving us n - 1 sorts of decreasing size. Summing k log k from k = n down to k = 2 yields O(n² log n).

Space Complexity: O(1) extra

We sort in place and modify the existing list. Only a constant number of temporary variables (x, y) are used beyond the input.

Why This Approach Is Not Efficient

The brute force sorts the entire collection from scratch every round, even though only one element changed (the remaining piece was inserted). Sorting is O(n log n) work, and doing it n times gives O(n² log n) total.

The fundamental problem: we only need the two largest elements each round, but sorting gives us the full ordering — far more information than we need.

Key insight: A max heap (priority queue) is a data structure designed exactly for this: extract the maximum element in O(log n) time and insert a new element in O(log n) time. Instead of sorting the whole array for O(n log n) per round, we can extract two maximums in O(log n) each and optionally insert the difference in O(log n) — that is O(log n) per round instead of O(n log n). Over n rounds, this brings the total from O(n² log n) down to O(n log n).

Bar chart comparing O(n² log n) brute force versus O(n log n) max heap for n = 30 stones
Bar chart comparing O(n² log n) brute force versus O(n log n) max heap for n = 30 stones

Optimal Approach - Max Heap

Intuition

A heap (also called a priority queue) is a tree-shaped data structure where the parent is always larger than its children (in a max heap). This property means the root is always the largest element, so extracting the maximum is fast.

Think of a heap like a tournament bracket. The champion (root) is the strongest player. If the champion leaves, a quick mini-tournament among a few players determines the new champion — you do not need to replay the entire tournament from scratch.

For this problem:

  1. Build a max heap from all stone weights — this takes O(n) time.
  2. Each round: extract the top two elements (the two heaviest stones) in O(log n) each.
  3. If they differ, insert the difference back into the heap in O(log n).
  4. Stop when the heap has one or zero elements.

In Python, the heapq module provides a min heap, so we negate all values to simulate a max heap. When we extract the minimum of the negated values, we are actually extracting the maximum of the original values.

This approach is both conceptually elegant and efficient: the heap automatically maintains the ordering as elements are extracted and inserted, with no wasted work.

Step-by-Step Explanation

Let's trace through stones = [2, 7, 4, 1, 8, 1]:

Step 1: Build a max heap from the stones → [8, 7, 4, 1, 2, 1]. The largest value (8) is at the root.

Step 2: Extract max → 8. Heap re-balances to [7, 2, 4, 1, 1].

Step 3: Extract max → 7. Heap becomes [4, 2, 1, 1].

Step 4: Smash 8 and 7. Not equal: 8 - 7 = 1. Insert 1 back into the heap → [4, 2, 1, 1, 1]. The heap property is maintained after insertion.

Step 5: Extract max → 4. Heap becomes [2, 1, 1, 1].

Step 6: Extract max → 2. Heap becomes [1, 1, 1].

Step 7: Smash 4 and 2. Not equal: 4 - 2 = 2. Insert 2 → [2, 1, 1, 1].

Step 8: Extract max → 2. Heap becomes [1, 1, 1].

Step 9: Extract max → 1. Heap becomes [1, 1].

Step 10: Smash 2 and 1. Not equal: 2 - 1 = 1. Insert 1 → [1, 1, 1].

Step 11: Extract max → 1. Heap becomes [1, 1].

Step 12: Extract max → 1. Heap becomes [1].

Step 13: Smash 1 and 1. Equal — both destroyed. Do not insert anything.

Step 14: Heap has 1 element left. Return 1.

Max Heap — Extract Two Heaviest, Smash, Re-Insert — Watch how the max heap always keeps the heaviest stone at the root, making extraction O(log n) instead of requiring a full sort each round.

Algorithm

  1. Build a max heap from all stone weights (O(n) heapify)
  2. While the heap has more than 1 element:
    a. Extract the maximum element y (heaviest stone)
    b. Extract the new maximum element x (second heaviest)
    c. If x ≠ y, insert y - x back into the heap
    d. If x == y, do nothing (both stones destroyed)
  3. If the heap is empty, return 0
  4. Otherwise return the single remaining element

Note for Python: Python's heapq module only supports a min heap. To simulate a max heap, negate all values when inserting and negate again when extracting.

Code

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> maxHeap(stones.begin(), stones.end());

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

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

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        # Negate values to simulate max heap with Python's min heap
        max_heap = [-s for s in stones]
        heapq.heapify(max_heap)

        while len(max_heap) > 1:
            y = -heapq.heappop(max_heap)  # heaviest
            x = -heapq.heappop(max_heap)  # second heaviest
            if x != y:
                heapq.heappush(max_heap, -(y - x))

        return -max_heap[0] if max_heap else 0
import java.util.*;

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) maxHeap.offer(s);

        while (maxHeap.size() > 1) {
            int y = maxHeap.poll();
            int x = maxHeap.poll();
            if (x != y) {
                maxHeap.offer(y - x);
            }
        }

        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Building the heap takes O(n). Each round performs at most 2 extractions and 1 insertion, each costing O(log n). There are at most n - 1 rounds, so the total heap operation cost is O(n log n). Combined: O(n) + O(n log n) = O(n log n).

Space Complexity: O(n)

The heap stores all n stone weights. In languages like Python where we create a separate negated list, this is O(n) extra space. In C++ or Java using a priority queue built from the input, it is also O(n) for the internal storage of the heap.