Last Stone Weight

Easy Heaps Top K / Kth Largest / Smallest Original on LeetCode

Reported atNvidiaPayPal

Last Stone Weight is a easy heaps problem solved with the top k / kth largest / smallest pattern. The best approach, optimal (max-heap), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort every round) up.

Problem

You have a pile of stones, where stones[i] is the weight of the i-th stone. On each turn you take the two heaviest stones, with weights y >= x, and smash them together:

  • if x == y, both stones are destroyed;
  • otherwise the lighter stone is destroyed and the heavier one now weighs y - x.

Keep going until at most one stone is left. Return the weight of that stone, or 0 if no stones remain.

Examples

Example 1

Input
stones = [4, 9, 3, 6]
Output
2
Why
9 and 6 leave 3 → [4, 3, 3]; 4 and 3 leave 1 → [3, 1]; 3 and 1 leave 2 → [2].

Example 2

Input
stones = [5, 5]
Output
0
Why
Equal stones destroy each other, so nothing is left.

Example 3

Input
stones = [8]
Output
8
Why
A single stone is never smashed.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (sort every round)O(n² log n)O(n)
Optimal (max-heap)O(n log n)O(n)

1Brute force (sort every round)

TimeO(n² log n)Up to n rounds, each sorting up to n stones.
SpaceO(n)The working list.

Keep the stones in a list. Each round, sort it, take the two largest, and put back their difference if it is positive. Stop when at most one stone is left.

  1. Copy the stones into a list.
  2. While the list has at least two stones: sort it, remove the last two values y >= x.
  3. If y > x, add y - x back to the list.
  4. Return the remaining stone, or 0 if the list is empty.
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 (y > x) list.add(y - x);
        }
        return list.isEmpty() ? 0 : list.get(0);
    }
}

2Optimal (max-heap)

TimeO(n log n)Each round removes at least one stone, so there are at most n rounds of O(log n) heap work.
SpaceO(n)The heap holds up to n stones.

A max-heap always hands out the current heaviest stone in O(log n). Pop the two heaviest, push back their difference when it is non-zero, and repeat until at most one stone remains.

  1. Push every stone into a max-heap.
  2. While the heap has at least two stones: pop y, pop x.
  3. If y != x, push y - x.
  4. Return the top of the heap, or 0 if it is empty.
class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) pq.offer(s);
        while (pq.size() > 1) {
            int y = pq.poll(), x = pq.poll();
            if (y != x) pq.offer(y - x);
        }
        return pq.isEmpty() ? 0 : pq.peek();
    }
}

Edge cases to test

  • Only one stone
  • Two equal stones (nothing left)
  • All stones equal
  • One stone much heavier than all others combined

Hints

Hint 1

At every turn you need the two largest values. Which data structure gives the maximum quickly and stays updated after insertions?

Hint 2

Use a max-heap: pop two, push back their difference if it is not zero.

FAQ

What is the best time complexity for Last Stone Weight?

Optimal (max-heap) runs in O(n log n) time and O(n) extra space. Each round removes at least one stone, so there are at most n rounds of O(log n) heap work.

Which pattern does Last Stone Weight use?

It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Kth Largest Element in a Stream, Top K Frequent Words.

Is there a brute force solution for Last Stone Weight?

Yes. Brute force (sort every round) takes O(n² log n) time and O(n) space. Keep the stones in a list.

Which edge cases should I test for Last Stone Weight?

Only one stone; Two equal stones (nothing left); All stones equal; One stone much heavier than all others combined.