1046. Last Stone Weight LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 1046. Last Stone Weight LeetCode Solution with the best time and space complexity. The solution to Last Stone Weight problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Last Stone Weight solution in C++
Last Stone Weight solution in Java
Last Stone Weight solution in Python
Additional Resources

1046. Last Stone Weight LeetCode Solution image

Problem Statement of Last Stone Weight

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

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

1046. Last Stone Weight LeetCode Solution in C++

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

    while (pq.size() >= 2) {
      const int n1 = pq.top();
      pq.pop();
      const int n2 = pq.top();
      pq.pop();
      if (n1 != n2)
        pq.push(n1 - n2);
    }

    return pq.empty() ? 0 : pq.top();
  }
};
/* code provided by PROGIEZ */

1046. Last Stone Weight LeetCode Solution in Java

class Solution {
  public int lastStoneWeight(int[] stones) {
    Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

    for (final int stone : stones)
      pq.offer(stone);

    while (pq.size() >= 2) {
      final int n1 = pq.poll();
      final int n2 = pq.poll();
      if (n1 != n2)
        pq.offer(n1 - n2);
    }

    return pq.isEmpty() ? 0 : pq.peek();
  }
}
// code provided by PROGIEZ

1046. Last Stone Weight LeetCode Solution in Python

class Solution:
  def lastStoneWeight(self, stones: list[int]) -> int:
    pq = [-stone for stone in stones]
    heapq.heapify(pq)

    while len(pq) >= 2:
      n1 = -heapq.heappop(pq)
      n2 = -heapq.heappop(pq)
      if n1 != n2:
        heapq.heappush(pq, -(n1 - n2))

    return 0 if not pq else -pq[0]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents