Start learning free

LESSON 292 OF 347 · HEAP

Last Stone Weight in C#: Simulating with a Max Heap

Practice O(n log n) Read the full explanation

We have a collection of stones, where each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

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

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

 

Example: 

Input: [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.
STEP 1 OF 9
    Ctrl + Enter to check

    C# · HEAP

    Last Stone Weight in C#, explained

    Problem overview

    The method LastStoneWeight receives an array stones of positive weights. Each turn, the two heaviest stones are smashed together. If they weigh the same, both disappear. Otherwise the lighter one disappears and the heavier one stays, with the weight reduced by the lighter one's weight. After enough turns, at most one stone remains, and the method returns its weight, or 0 if no stone is left.

    For [2, 7, 4, 1, 8, 1] the process looks like this:

    • 8 and 7 smash into a stone of weight 1, leaving 2, 4, 1, 1, 1.
    • 4 and 2 smash into 2, leaving 2, 1, 1, 1.
    • 2 and 1 smash into 1, leaving 1, 1, 1.
    • 1 and 1 destroy each other, leaving a single 1.

    The answer is 1.

    Approach: always pull out the two heaviest

    The rules say what to do every turn: find the two heaviest stones, remove them, and possibly insert one new stone. Scanning the array for the two largest values on every turn costs O(n), and sorting it after every insertion costs even more.

    A max heap fits exactly. It is a structure that always hands back its largest element, and both removing it and inserting a new element cost O(log n). The plan is to load every stone into the heap, then repeat: take out two stones, and if their weights differ, put the difference back. When fewer than two stones remain, the simulation is over.

    Each turn removes at least one stone from the heap, so there are fewer than n turns. With O(log n) per heap operation, the total is O(n log n).

    Step by step

    1. Create the heap. In C#, PriorityQueue<int, int> stores an element together with a priority and gives back the element with the lowest priority first. A comparer that reverses the comparison, (x, y) => y - x, makes the heaviest stone come out first.
    2. Loop over stones with foreach, using stone as the loop variable.
    3. Enqueue each stone. heap.Enqueue(stone, stone) uses the stone's weight as both the element and its priority.
    4. Loop while heap.Count >= 2. A smash needs two stones.
    5. Dequeue the heaviest stone into x.
    6. Dequeue the next heaviest into y. Since x came out first, x >= y.
    7. Put back the remainder. If x != y, the stone x - y goes back into the heap. If they are equal, nothing goes back, which means both stones are destroyed.
    8. Handle the empty case. After the loop, if heap.Count == 0, every stone has been destroyed, so return 0.
    9. Return the survivor. Otherwise exactly one stone is left, and heap.Peek() returns it without removing it.

    The solution in C#

    class Solution {
    public int LastStoneWeight(int[] stones) {
        PriorityQueue<int, int> heap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y - x));
        foreach (int stone in stones) {
            heap.Enqueue(stone, stone);
        }
        while (heap.Count >= 2) {
            int x = heap.Dequeue();
            int y = heap.Dequeue();
            if (x != y) {
                heap.Enqueue(x - y, x - y);
            }
        }
        if (heap.Count == 0) {
            return 0;
        }
        return heap.Peek();
    }
}

    Some C# details to notice:

    • Elements and priorities are separate. Enqueue(element, priority) takes two arguments, while Dequeue() and Peek() return only the element. Because every stone is its own priority, the element that comes out is also the weight.
    • The reversing comparer. Comparer<int>.Create builds a comparer from a lambda. For two priorities, a negative result means the first should come out first. y - x is negative when x is greater than y, so larger weights come out first.
    • Subtraction in comparers can overflow. int arithmetic wraps silently, so y - x is wrong for extreme values such as int.MinValue. Positive weights avoid the problem, since the difference of two positive numbers always fits in an int. For general data, y.CompareTo(x) is the safe form.
    • Naming. The lambda parameters x and y are separate from the local variables x and y in the loop. They live in different scopes, and the lambda is only a short function passed to Create.
    • Count is a property. Write heap.Count without parentheses. Dequeue() and Peek() are methods.
    • Empty queues throw. Dequeue() or Peek() on an empty PriorityQueue throws an InvalidOperationException. That is why the code checks Count before every use.

    Complexity

    Time: O(n log n). Loading the heap takes n insertions of O(log n) each. The loop runs fewer than n times, because each turn removes two stones and returns at most one. Every turn performs two removals and at most one insertion, all O(log n).

    Space: O(n). The heap holds up to n stones at the start.

    Edge cases and common mistakes

    • Everything cancels out. For [3, 3] the two stones destroy each other, nothing is put back, and the method returns 0.
    • A single stone. For [5] the loop never runs, and Peek() returns 5.
    • No stones. For an empty array the heap is empty and the method returns 0. Without the Count == 0 check, Peek() would throw.
    • Forgetting to reverse the order. A PriorityQueue created without a comparer is a min heap, and the method would smash the two lightest stones.
    • Putting back the wrong value. Enqueue the difference, x - y, with the same value as priority. Using the old weight as the priority would keep the new stone in the wrong place in the order.
    • Swapped roles. Because the heap returns the heavier stone first, x - y is never negative. If you dequeue in the other order, you would need an absolute value.

    Testing

    • stones = [2, 7, 4, 1, 8, 1] gives 1.
    • stones = [3, 3] gives 0.
    • stones = [5] gives 5.
    • stones = [] gives 0.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free