Skip to content

1046. Last Stone Weight 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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]