# Last Stone Weight
**Difficulty:** EASY
[External](https://leetcode.com/problems/last-stone-weight)
Canonical: https://scaleengineer.com/dsa/problems/last-stone-weight
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Nvidia](https://scaleengineer.com/companies/nvidia), [PayPal](https://scaleengineer.com/companies/paypal), [Rippling](https://scaleengineer.com/companies/rippling)
---
## Problem
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
## Simulation with Repeated Sorting
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.
**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.
**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`).
### Explanation
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.

```java
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);
    }
}
```
### 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.

## Simulation with Bucket Sort
Since the weights of the stones are limited to a relatively small range (1 to 1000), we can use an array as a frequency map (also known as bucket sort or counting sort). This allows us to keep track of the counts of stones of each weight and simulate the process without using a comparison-based sort or a heap data structure.
**Time:** O(n + W), where `n` is the number of stones and `W` is the maximum possible weight. It takes `O(n)` to build the buckets and `O(W)` for the main simulation loop. · **Space:** O(W), where `W` is the maximum possible weight of a stone (1000). This is for the `buckets` array.
**Pros:** Efficient when the range of weights `W` is small.; Avoids comparison-based sorting and the `log n` factor associated with heaps.
**Cons:** The logic can be more complex to implement correctly compared to the heap-based solution.; Its performance is dependent on the maximum weight `W`. If `W` were very large, this approach would be inefficient.; For the given constraints (`n <= 30`, `W <= 1000`), this is slightly slower than the heap approach.
### Explanation
We create an array, say `buckets`, of size 1001, where `buckets[w]` stores the number of stones with weight `w`. After populating this array, we simulate the smashing process by iterating downwards from the maximum possible weight (1000). We use a pointer `w` for the current weight and a variable `heaviest` to keep track of the first heavy stone found in a smash pair.

The simulation iterates from `w = 1000` down to 1. When we find a weight `w` with a non-zero count, we check if we already have a `heaviest` stone from a previous, larger weight. If not, we handle all pairs of stones of weight `w` (which smash to nothing) and if one is left over, it becomes the new `heaviest`. If we do have a `heaviest` stone, we smash it with the current stone of weight `w`, calculate the remainder, and update its count in the `buckets` array. This new stone will be processed when the loop pointer `w` reaches its weight.

```java
class Solution {
    public int lastStoneWeight(int[] stones) {
        int[] buckets = new int[1001];
        for (int stone : stones) {
            buckets[stone]++;
        }

        int heaviest = 0; // To store the weight of the first stone in a smash
        int w = 1000; // Current weight we are looking at

        while (w > 0) {
            if (buckets[w] == 0) {
                w--;
                continue;
            }
            
            if (heaviest == 0) {
                // This is the first stone of a potential smash.
                // All pairs of weight 'w' smash to 0.
                if (buckets[w] % 2 == 1) {
                    // If there's an odd number, one 'w' is left over.
                    heaviest = w;
                }
                // Move to the next smaller weight.
                w--;
            } else {
                // We have a 'heaviest' stone and now found a stone of weight 'w'.
                // Smash them.
                buckets[w]--; // Use one stone of weight 'w'.
                int newWeight = heaviest - w;
                buckets[newWeight]++;
                heaviest = 0; // Reset heaviest as it has been used.
                // We stay at 'w' to process remaining stones of this weight.
            }
        }
        return heaviest;
    }
}
```
### Algorithm
- Create a `buckets` array of size 1001 (since max weight is 1000) to store the frequency of each stone weight.
- Populate the `buckets` array by iterating through the input `stones`.
- Initialize a variable `heaviest = 0` to hold the first of two stones to be smashed, and a pointer `w = 1000`.
- Loop `w` from 1000 down to 1:
  - If `buckets[w]` is 0, continue to the next smaller weight.
  - If `heaviest` is 0, it means we're looking for the first stone. Any pairs of stones of weight `w` will smash each other. If `buckets[w]` is odd, one stone is left over; we set `heaviest = w` and move to the next smaller weight (`w--`).
  - If `heaviest` is not 0, we have found our second stone (`w`). We smash them: decrement `buckets[w]`, calculate `newWeight = heaviest - w`, increment `buckets[newWeight]`, and reset `heaviest = 0`. We do not decrement `w` yet, as there might be more stones of this weight to process.
- After the loop, `heaviest` will hold the weight of the last stone, or 0.

## Optimal Approach using a Max-Heap
The problem requires repeatedly finding and removing the two largest elements from a collection. A max-heap is the ideal data structure for this task. It provides `O(log n)` time complexity for insertions and for extracting the maximum element, making it highly efficient for this problem.
**Time:** O(n log n). Building the heap by adding `n` elements takes `O(n log n)`. The loop runs `n-1` times, and each iteration involves two `poll` operations and at most one `add` operation, each taking `O(log k)` time where `k` is the current heap size. This gives a total time complexity of `O(n log n)`. · **Space:** O(n) to store the `n` stones in the priority queue.
**Pros:** This is the most efficient and standard solution for this type of problem.; The code is clean, easy to reason about, and performs well for any `n`.
**Cons:** Requires knowledge of the Priority Queue / Heap data structure.
### Explanation
A max-heap is a specialized tree-based data structure that satisfies the heap property: the value of each node is greater than or equal to the value of its children. This ensures the root of the tree is always the maximum element in the collection.

The algorithm is as follows:
1.  Create a max-heap. In Java, this can be done with `new PriorityQueue<>(Collections.reverseOrder())`.
2.  Insert all the stone weights from the input array into the max-heap. Building the heap takes `O(n log n)` time.
3.  Loop as long as the heap contains more than one element.
4.  In each iteration, extract the two largest elements by calling the `poll()` method twice. Let these be `y` (the largest) and `x` (the second largest).
5.  If `y` is greater than `x`, a new stone with weight `y - x` is formed. Insert this new weight back into the heap.
6.  If `x` and `y` are equal, both are destroyed, and nothing is added back to the heap.

When the loop finishes, the heap will have at most one stone. If the heap is empty, we return 0. Otherwise, we return the weight of the single remaining stone, which is at the top of the heap.

```java
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int lastStoneWeight(int[] stones) {
        // Create a max-heap by providing a reverse order comparator.
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // Add all stones to the max-heap.
        for (int stone : stones) {
            maxHeap.add(stone);
        }

        // While there are at least two stones...
        while (maxHeap.size() > 1) {
            // Get the two heaviest stones.
            int y = maxHeap.poll();
            int x = maxHeap.poll();

            // If they are not equal, smash them and add the remainder.
            if (y > x) {
                maxHeap.add(y - x);
            }
            // If they are equal, they are both destroyed.
        }

        // If there is a stone left, return its weight, otherwise return 0.
        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}
```
### Algorithm
- Create a max-heap. In Java, this is a `PriorityQueue` with a reverse order comparator.
- Add all elements from the `stones` array to the heap.
- Loop while the heap's size is greater than 1.
- In each iteration, `poll()` the two largest elements, `y` and `x`.
- If `y > x`, `add` the difference `y - x` back to the heap.
- After the loop, if the heap is not empty, return the top element using `peek()`. Otherwise, return 0.

# Solutions
### Python

```python
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]

```

### Java

```java
class Solution {
public
  int lastStoneWeight(int[] stones) {
    PriorityQueue<Integer> q = new PriorityQueue<>((a, b)->b - a);
    for (int x : stones) {
      q.offer(x);
    }
    while (q.size() > 1) {
      int y = q.poll();
      int x = q.poll();
      if (x != y) {
        q.offer(y - x);
      }
    }
    return q.isEmpty() ? 0 : q.poll();
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} stones * @return {number} */ var lastStoneWeight =
  function (stones) {
    const pq = new MaxPriorityQueue();
    for (const x of stones) {
      pq.enqueue(x);
    }
    while (pq.size() > 1) {
      const y = pq.dequeue()[" priority "];
      const x = pq.dequeue()[" priority "];
      if (x != y) {
        pq.enqueue(y - x);
      }
    }
    return pq.isEmpty() ? 0 : pq.dequeue()[" priority "];
  };

```

### CPP

```cpp
class Solution {
public:
  int lastStoneWeight(vector<int> &stones) {
    priority_queue<int> pq;
    for (int x : stones) {
      pq.push(x);
    }
    while (pq.size() > 1) {
      int y = pq.top();
      pq.pop();
      int x = pq.top();
      pq.pop();
      if (x != y) {
        pq.push(y - x);
      }
    }
    return pq.empty() ? 0 : pq.top();
  }
};

```