Last Stone Weight easy

Problem Statement

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.
• If x != y, the remaining stone has 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 1

Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1. The array becomes [2,4,1,1,1]. We combine 4 and 2 to get 2. The array becomes [2,1,1,1]. We combine 2 and 1 to get 1. The array becomes [1,1,1]. We combine 1 and 1 to get 0. The array becomes [1]. Thus, we have 1 stone left.

Example 2

Input: stones = [1] Output: 1

Steps

1. Sort: Sort the stones array in descending order. This allows us to easily access the two heaviest stones.
2. Iterative Smashing: While there are at least two stones:
   • Take the two heaviest stones (first two elements of the sorted array).
   • Smash them: Calculate the difference (or 0 if they are equal).
   • Add the result (if non-zero) back to the array.
   • Re-sort the array.
3. Return the Result: After the loop, if there's one stone left, return its weight; otherwise, return 0.

Explanation

The problem can be solved efficiently using a priority queue (heap) data structure. However, for simplicity and clarity, the solution below uses sorting. Sorting allows us to easily find the two largest elements in each iteration. The iterative process simulates the smashing until only one or zero stones remain.

Code

import heapq

def lastStoneWeight(stones):
    """
    Finds the weight of the last stone remaining after smashing.

    Args:
        stones: A list of integers representing the weights of the stones.

    Returns:
        The weight of the last stone, or 0 if no stones are left.
    """
    stones = [-s for s in stones] #negate for max heap
    heapq.heapify(stones)

    while len(stones) > 1:
        y = -heapq.heappop(stones)  # Get the largest stone (negate to get positive value)
        x = -heapq.heappop(stones)  # Get the second largest stone
        if y > x:
            heapq.heappush(stones, -(y - x)) #Add the difference back to the heap
    return -stones[0] if stones else 0 #Return the last stone (negate to get positive value)

#Alternative solution without heapq, using sorting:
def lastStoneWeight_sorting(stones):
    while len(stones) > 1:
        stones.sort(reverse=True)
        x = stones.pop(0)
        y = stones.pop(0)
        if x != y:
            stones.append(x - y)
    return stones[0] if stones else 0

Complexity

Time Complexity: O(N log N) due to sorting in each iteration, where N is the number of stones. The while loop iterates at most N times.

Space Complexity: O(N) in the worst case (using sorting) to store the stones array. The heapq solution also uses O(N) space for the heap.