algoadvance

Leetcode 1046. Last Stone Weight

Problem Statement

We are given a list of stones’ weights. 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 destroyed.
• If x != y, the stone of weight x is destroyed, and the stone of weight y has a new weight y - x.

At the end of the game, there is at most one 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

Clarifying Questions

1. What’s the expected input size?
   • The number of stones n could be up to 30.
2. Can the weight of stones be negative or zero?
   • No, stone weights are positive integers.
3. What should be the return value if the input list is empty?
   • If there are no stones to begin with, the return value should be 0.

Strategy

1. Utilize a Max Heap:
   • Use a priority queue (max heap) to facilitate extraction of the two heaviest stones efficiently.
2. Algorithm:
   • Insert all stone weights into the max-heap.
   • While there is more than one stone left in the heap:
     • Extract the two heaviest stones.
     • If they are of equal weight, discard both.
     • If they are not of equal weight, insert the difference back into the heap.
   • At the end of the process, if the heap is empty, return 0. Otherwise, return the weight of the remaining stone.
3. Java Implementation:
   • Use PriorityQueue with Collections.reverseOrder to simulate max-heap.

Code

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

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

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

        // Process the stones
        while (maxHeap.size() > 1) {
            int first = maxHeap.poll();
            int second = maxHeap.poll();

            if (first != second) {
                maxHeap.add(first - second);
            }
        }

        return maxHeap.isEmpty() ? 0 : maxHeap.poll();
    }

    public static void main(String[] args) {
        LastStoneWeight solution = new LastStoneWeight();
        int[] stones = {2, 7, 4, 1, 8, 1};
        System.out.println(solution.lastStoneWeight(stones));  // Output: 1
    }
}

Time Complexity

• Building the max heap takes O(n log n) time where n is the number of stones.
• Each pairing and reinsertion operation has a time complexity of O(log n).
• In the worst case, we have to perform n-1 such operations.

Overall, the time complexity is approximately O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?