1046. Last Stone Weight

EasyArrayHeap (Priority Queue)
Leetcode Link

Problem Description

In this problem, we have a collection of stones with different weights, given in an array stones, where each stone's weight is represented by stones[i]. We are simulating a game where we repeatedly smash the two heaviest stones together and determine the outcome according to the following rules:

  • If both stones have the same weight (x == y), both stones get completely destroyed.
  • If the weights are different (x != y), the lighter stone gets destroyed, and the weight of the heavier stone gets reduced by that of the lighter stone (y - x).

The game continues until there is either one stone left or no stones remaining. The goal is to return the weight of the last remaining stone. If there are no stones left as a result of the smashes, we should return 0.

Intuition

The solution requires us to repeatedly find and remove the two heaviest stones. Since we need to do this repeatedly, a heap is an ideal data structure as it allows for efficient retrieval and updating of the largest elements.

A max heap keeps the maximum element at the top. However, Python's heapq module provides a min heap, so we insert the negative of stone weights to simulate the behavior of a max heap.

Here is the step-by-step approach to the solution:

  1. Convert all stone weights to their negative and create a min heap. This negation is necessary because the Python heapq module only supports min heaps.
  2. While there are at least two stones in the heap:
    1. Pop the heaviest stone (which is the smallest in the min heap due to negation) and store its negated value in y.
    2. Pop the second heaviest stone (again the smallest in our min heap) and store its negated value in x.
    3. If x and y are not equal, we push the weight difference negated (x - y) back onto the heap since stone x got destroyed and the weight of stone y reduced by x.
  3. After the loop, if the heap is empty, it means no stones are left and we return 0. Else, we return the negation of the weight of the last stone left in the heap (as we stored negative values, we need to negate it back to return the actual weight).

Using this approach, we efficiently simulate the stone smashing game and find the weight of the last stone or determine that no stones are left.

Learn more about Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Solution Approach

The method lastStoneWeight is implemented using a min heap to efficiently manage the stones according to their weights.

Here's a breakdown of the solution:

  • A min heap is created from the list of stones. Each stone's weight is negated prior to insertion because Python's heapq module works as a min heap. A min heap allows quick access to the smallest element, so by negating the weights, we get quick access to the largest element.
1h = [-x for x in stones]
2heapify(h)

  • The solution iteratively processes the heap until there’s one or zero stones left. This is handled by a while loop that continues as long as the length of the heap (h) is greater than one.

  • Inside the loop, the two heaviest stones (which are actually the two smallest values in the heap due to negation) are popped from the heap. This is done using heappop(h), and the negated value of the pops represents y and x.

1y, x = -heappop(h), -heappop(h)
  • If the weight of the two stones is not equal (x != y), it means that after smashing the stones, one of them (the lighter stone x) is completely destroyed, while the other (y) is reduced in weight. The difference (y - x) is computed, negated, and pushed back into the heap.
1if x != y:
2    heappush(h, x - y)
  • After the loop exits, which happens when only one stone is left or none at all, the function checks if the heap is empty. If it is empty (not h), the function returns 0. Otherwise, it returns the weight of the last stone left, negating it to convert it back to the original weight value.
1return 0 if not h else -h[0]

Using heapq for maintaining a heap and negating values is an efficient approach to simulate a max heap in Python. This problem showcases an excellent use of the heap data structure to solve a problem related to constant removal and insertion of elements to achieve a sorted characteristic (largest or smallest).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's consider a small example to illustrate the solution approach: Suppose we have an array of stone weights stones = [2, 7, 4, 1, 8, 1]. We need to perform the following steps:

  1. Convert the weights to their negative and create a min heap:

    • We negate the weights: [-2, -7, -4, -1, -8, -1]
    • Create a min heap from these negated weights: h = [-8, -7, -4, -1, -2, -1]

  2. While there are at least two stones in the heap:

    1. Pop the heaviest stone (smallest in negated form):
      • y = -heappop(h) gives us y = 8, and now h = [-7, -2, -4, -1, -1]
    2. Pop the second heaviest stone:
      • x = -heappop(h) gives us x = 7, and now h = [-4, -2, -1, -1]
    3. Push the weight difference negated back onto the heap since x != y:
      • The difference is 8 - 7 = 1. After negating, we push -1 back onto the heap.
      • Now, h = [-4, -2, -1, -1, -1]

  3. Repeat the process:

    • Next, y = -heappop(h) gives us y = 4, h = [-2, -1, -1, -1]
    • Then, x = -heappop(h) gives us x = 2, h = [-1, -1, -1]
    • The difference is 4 - 2 = 2. After negating, we push -2 back onto the heap.
    • Now, h = [-2, -1, -1]

  4. Continue:

    • Next, y = -heappop(h) gives us y = 2, h = [-1, -1]
    • Then, x = -heappop(h) gives us x = 1, h = [-1]
    • The difference is 2 - 1 = 1. After negating, we push -1 back onto the heap.
    • Now, h = [-1, -1]

  5. Final iterations will destroy both of the stones because they have the same weight:

    • Next, y = -heappop(h) gives us y = 1, h = [-1]
    • Then, x = -heappop(h) gives us x = 1, h = []
    • Since x == y, we don't push anything back onto the heap.

  6. Now the heap is empty (h = []), that is, no stones are left. We return 0.

The final result for the example input stones = [2, 7, 4, 1, 8, 1] is 0, as all stones are eventually destroyed.

Solution Implementation

1from heapq import heapify, heappush, heappop
2
3class Solution:
4    def lastStoneWeight(self, stones: List[int]) -> int:
5        # Create a max heap by inverting the values of the stones
6        max_heap = [-stone for stone in stones]
7        heapify(max_heap)
8
9        # Continue processing until there is one or no stones left
10        while len(max_heap) > 1:
11            # Pop the two largest stones from the heap
12            # Stones are negated again to get their original values
13            stone1 = -heappop(max_heap)
14            stone2 = -heappop(max_heap)
15
16            # If the largest stones are not of the same weight
17            if stone1 != stone2:
18                # The result of the collision is added back to the heap
19                heappush(max_heap, -(stone1 - stone2))
20
21        # If the heap is empty, return 0; else return the weight of the last stone
22        return 0 if not max_heap else -max_heap[0]
23
1class Solution {
2    /**
3     * Simulate the process of smashing stones together and return
4     * the weight of the last remaining stone (if any).
5     * 
6     * @param stones An array of stone weights.
7     * @return The weight of the last stone, or 0 if no stones are left.
8     */
9    public int lastStoneWeight(int[] stones) {
10        // Create a max-heap to store and compare the stone weights in descending order
11        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
12
13        // Add all stone weights to the max-heap
14        for (int stone : stones) {
15            maxHeap.offer(stone);
16        }
17
18        // Continue until there is only one stone left or none at all
19        while (maxHeap.size() > 1) {
20            // Get the two heaviest stones
21            int stoneOne = maxHeap.poll();
22            int stoneTwo = maxHeap.poll();
23
24            // If they are not the same weight, put the difference back into the max-heap
25            if (stoneOne != stoneTwo) {
26                maxHeap.offer(stoneOne - stoneTwo);
27            }
28            // If they are equal, both stones are completely smashed, and nothing is added back
29        }
30
31        // Return the last stone's weight or 0 if no stones are left
32        return maxHeap.isEmpty() ? 0 : maxHeap.poll();
33    }
34}
35
1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    // Function to return the last stone's weight after smashing the largest two until one or none are left
7    int lastStoneWeight(vector<int>& stones) {
8        // Priority queue to store the stones with max heap property to easily retrieve the heaviest stones
9        priority_queue<int> maxHeap;
10
11        // Insert all stones into the priority queue
12        for (int stone : stones) {
13            maxHeap.push(stone);
14        }
15
16        // Loop until there is only one stone left or none
17        while (maxHeap.size() > 1) {
18            // Take out the heaviest stone
19            int heaviestStone = maxHeap.top();
20            maxHeap.pop();
21
22            // Take out the second heaviest stone
23            int secondHeaviestStone = maxHeap.top();
24            maxHeap.pop();
25
26            // If the two stones have different weights, push the difference back into the queue
27            if (heaviestStone != secondHeaviestStone) {
28                maxHeap.push(heaviestStone - secondHeaviestStone);
29            }
30
31            // If the stones have the same weight, both get destroyed and nothing goes back into the queue
32        }
33
34        // If there are no stones left, return 0, otherwise return the weight of the remaining stone
35        return maxHeap.empty() ? 0 : maxHeap.top();
36    }
37};
38
1// Import the necessary module for Priority Queue
2import { MaxPriorityQueue } from '@datastructures-js/priority-queue';
3
4/**
5 * Simulates a process where stones smash each other. If two stones have 
6 * different weights, the weight of the smaller one is subtracted from the other.
7 * The smaller stone is then considered destroyed. The process repeats until
8 * there is one stone left or none. The function returns the weight of the remaining
9 * stone, or 0 if none are left.
10 * @param {number[]} stones - An array of stone weights.
11 * @return {number} The weight of the last remaining stone, or 0 if none.
12 */
13function getLastStoneWeight(stones: number[]): number {
14    // Initialize a max priority queue for the stones
15    const priorityQueue = new MaxPriorityQueue<number>();
16  
17    // Enqueue all the stones to the priority queue
18    for (const stone of stones) {
19        priorityQueue.enqueue(stone);
20    }
21
22    // Loop until there is either one stone left or none
23    while (priorityQueue.size() > 1) {
24        // Dequeue the two heaviest stones
25        const heavierStone = priorityQueue.dequeue().element;
26        const lighterStone = priorityQueue.dequeue().element;
27
28        // If there is a weight difference, enqueue the difference as a new stone
29        if (heavierStone !== lighterStone) {
30            priorityQueue.enqueue(heavierStone - lighterStone);
31        }
32    }
33
34    // If the priority queue is empty, return 0; otherwise, return the weight of the last stone
35    return priorityQueue.isEmpty() ? 0 : priorityQueue.dequeue().element;
36}
37
Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

The given code implements a heap to solve the last stone weight problem. Let's analyze both the time complexity and the space complexity of the given code.

Time Complexity

The main operations in the algorithm are:

  1. Converting the stones list into a heap which takes O(n) time, where n is the number of stones.
  2. The while loop. In the worst case, the heap contains n - 1 elements, and heappop() is called twice per iteration. Since each heappop() operation takes O(log n) time, and in each iteration, we might do a heappush() which also takes O(log n) time.
  3. The loop runs at most n - 1 times because in each iteration at least one stone is removed.

Putting it all together, the worst-case scenario would involve (2 * log n + log n) operations per iteration due to two heappop() calls and one potential heappush() call, across n - 1 iterations. Hence, the total time complexity is O(n log n).

Space Complexity

The space complexity consists of:

  1. The heap h which stores at most n integers, thus requiring O(n) space.
  2. Constant extra space for variables x and y.

So, the overall space complexity of the algorithm is O(n) since the heap size is proportional to the input size, and other space usage is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫