Scale Engineer

Last Stone Weight

Easy
#0999Time: O(n^2 log n). Let `n` be the initial number of stones. The loop runs up to `n-1` times. In each iteration `i`, we sort a list of size `n-i`, which takes `O((n-i) log (n-i))`. The total time is the sum of these sorting times, which is dominated by the earlier, larger sorts, leading to a complexity of `O(n^2 log n)`.Space: O(n) to store the stones in a list, where n is the initial number of stones.4 companies
Data structures
ArrayHeap (Priority Queue)
Companies
FlipkartNvidiaPayPalRippling

Prompt

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

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

 

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
Output: 1

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the stone-smashing process described in the problem. In each step, we need to find the two heaviest stones. A straightforward, albeit inefficient, way to do this is to sort the collection of stones in every iteration and pick the last two elements.

Algorithm

  • Convert the input array stones into a List.
  • Loop while the list size is greater than 1.
  • In each iteration, sort the list in ascending order.
  • Remove the last two elements (the heaviest stones), y and x.
  • If y > x, add the difference y - x back to the list.
  • After the loop, if the list is empty, return 0. Otherwise, return the single remaining element.

Walkthrough

We maintain a list of the current stone weights. The simulation proceeds in a loop that continues as long as there is more than one stone.

Inside the loop:

  1. Sort the list of stones in ascending order. This brings the heaviest stones to the end of the list.
  2. Identify the two heaviest stones, y (the last element) and x (the second-to-last element).
  3. Remove both x and y from the list.
  4. If their weights are different (x != y), calculate the new weight y - x and add it back to the list. If they are the same, they are both destroyed, and nothing is added back.

The loop terminates when one or zero stones remain. If the list is empty, the result is 0. Otherwise, the result is the weight of the single remaining stone.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public int lastStoneWeight(int[] stones) {        List<Integer> stoneList = new ArrayList<>();        for (int stone : stones) {            stoneList.add(stone);        }         while (stoneList.size() > 1) {            Collections.sort(stoneList);            int y = stoneList.remove(stoneList.size() - 1);            int x = stoneList.remove(stoneList.size() - 1);             if (y > x) {                stoneList.add(y - x);            }        }         return stoneList.isEmpty() ? 0 : stoneList.get(0);    }}

Complexity

Time

O(n^2 log n). Let `n` be the initial number of stones. The loop runs up to `n-1` times. In each iteration `i`, we sort a list of size `n-i`, which takes `O((n-i) log (n-i))`. The total time is the sum of these sorting times, which is dominated by the earlier, larger sorts, leading to a complexity of `O(n^2 log n)`.

Space

O(n) to store the stones in a list, where n is the initial number of stones.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the logic from the problem description.

Cons

  • Highly inefficient due to repeated sorting of the entire list in each step.

  • Would be too slow for a larger number of stones (n).

Solutions

class Solution:    def lastStoneWeight(self, stones: List[int]) -> int: h = [- x for x in stones] heapify(h) while len(h) > 1: y, x = - heappop(h), - heappop(h) if x != y: heappush(h, x - y) return 0 if not h else - h[0]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem