Last Stone Weight

Easy

PayPal

0 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given an array of integers stones where stones[i] is the weight of the i^th 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, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input: stones = [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.

Example 2:

Input: stones = [1]
Output: 1

Constraints:

1 <= stones.length <= 30
1 <= stones[i] <= 1000

Last Stone Weight

Easy

PayPal

0 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given an array of integers stones where stones[i] is the weight of the i^th 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, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input: stones = [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.

Example 2:

Input: stones = [1]
Output: 1

Constraints:

1 <= stones.length <= 30
1 <= stones[i] <= 1000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values (range) for the weight of each stone, and are they guaranteed to be non-negative?
What is the maximum number of stones that the input array can contain?
If the input array is empty or contains only one stone, what should the function return?
Are the stone weights guaranteed to be integers, or could they be floating-point numbers?
If there are multiple stones with the same maximum weight, how should I select the two heaviest stones for smashing (e.g., the first two occurrences, or is the order arbitrary)?

Brute Force Solution

Approach

The brute force method for the last stone weight problem involves simulating every possible combination of stone crushing until only one stone (or none) remains. We try every pair of stones, find the difference, and then try all pairs again with the updated collection of stones. This continues until we are left with zero or one stones.

Here's how the algorithm would work step-by-step:

Look at all possible pairs of stones.
For each pair, determine which stone is heavier.
Subtract the weight of the lighter stone from the weight of the heavier stone.
Remove both original stones from the collection.
Add the resulting difference (or the heavier stone's weight if the lighter stone was removed from an empty collection) back to the collection.
Repeat the process of finding pairs and crushing until only one stone or no stones are left.
If one stone remains, its weight is the final answer. If no stones remain, the final answer is zero.

Code Implementation

def last_stone_weight_brute_force(stones):
    while len(stones) > 1:
        heaviest_stone_index = 0
        second_heaviest_stone_index = 1

        # Find the two heaviest stones
        if stones[second_heaviest_stone_index] > stones[heaviest_stone_index]:
            heaviest_stone_index, second_heaviest_stone_index = second_heaviest_stone_index, heaviest_stone_index

        for index in range(2, len(stones)):
            if stones[index] > stones[heaviest_stone_index]:
                second_heaviest_stone_index = heaviest_stone_index
                heaviest_stone_index = index
            elif stones[index] > stones[second_heaviest_stone_index]:
                second_heaviest_stone_index = index

        # Simulate crushing the stones.
        if stones[heaviest_stone_index] == stones[second_heaviest_stone_index]:
            #Remove both stones since weights are equal
            if heaviest_stone_index > second_heaviest_stone_index:
                stones.pop(heaviest_stone_index)
                stones.pop(second_heaviest_stone_index)
            else:
                stones.pop(second_heaviest_stone_index)
                stones.pop(heaviest_stone_index)
        else:
            #Keep the difference after crushing
            stones[heaviest_stone_index] = stones[heaviest_stone_index] - stones[second_heaviest_stone_index]
            stones.pop(second_heaviest_stone_index)

    if len(stones) == 0:
        return 0
    else:
        return stones[0]

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach considers all possible pairs of stones. In the worst case, we might pick different pairs at each step, leading to a large number of combinations. Specifically, we are effectively permuting the order in which we pick stones to crush. Because we are essentially evaluating combinations of stone pairings until we reach a single or zero stones left, the number of possible crushing sequences grows factorially with the initial number of stones (n!). Thus the overall time complexity is O(n!).

Space Complexity

O(N) – The brute force method, as described, modifies the original collection of stones. Each time a pair of stones is crushed, the original stones are removed, and the resulting difference is added back. Since the stones are being directly manipulated within the input collection (stones), the collection itself serves as the primary data structure. In the worst-case scenario, where the crushing repeatedly results in new stones being added back until only one stone remains, the space used to store the collection of stones could still grow or stay equal to N, where N is the initial number of stones. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The problem asks us to simulate smashing stones together until only one (or none) remains. The most efficient approach is to always smash the two heaviest stones together at each step. This way, we quickly reduce the number of stones and focus on the most impactful operations.

Here's how the algorithm would work step-by-step:

First, find the two heaviest stones from the pile.
Smash these two stones together. There are two possibilities: either they have the same weight, or they have different weights.
If the stones have the same weight, both are destroyed, and we remove them from consideration.
If the stones have different weights, the lighter stone is destroyed, and the heavier stone is reduced in weight by the amount of the lighter stone's weight. Essentially, find the difference between the two stones.
Put the resulting stone (if any) back into the pile of stones.
Repeat this process of finding the two heaviest stones, smashing them, and updating the pile until there is at most one stone left.
If there is one stone left, its weight is the answer. If there are no stones left, the answer is zero.

Code Implementation

import heapq

def lastStoneWeight(stones):
    stones = [-stone for stone in stones]

    heapq.heapify(stones)

    while len(stones) > 1:
        # Get the two heaviest stones
        stone_one = heapq.heappop(stones)
        stone_two = heapq.heappop(stones)

        # If the stones are not equal, calculate the difference
        if stone_one != stone_two:

            # Push the difference back into the heap
            heapq.heappush(stones, stone_one - stone_two)

    # If there is a stone remaining return its weight
    if stones:
        return -stones[0]
    else:
        return 0

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation within the while loop (smashing stones) is finding the two heaviest stones. If we use a data structure like a max heap (priority queue) to store the stones, extracting the two heaviest stones takes O(log n) time, and inserting the resulting stone back into the heap also takes O(log n) time. Since in the worst case, we may need to perform this smashing operation until only one or zero stones remain (which could be up to n times), the overall time complexity is O(n log n). Building the initial heap takes O(n) time, which is dominated by the O(n log n) smashing operations.

Space Complexity

O(N) – The most significant space complexity arises from potentially storing all the stones in a data structure like a max heap to efficiently find the two heaviest stones. In the worst-case scenario, where stones are repeatedly smashed and the resulting stone is added back, we might need to hold almost all the stones at some point. Thus, the auxiliary space required to maintain this data structure is proportional to the number of stones, N. Therefore the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no stones to smash.
Input array with a single stone	Return the weight of the single stone directly.
Input array with two stones of equal weight	The stones are destroyed, resulting in 0, so the algorithm should correctly handle this scenario and return 0.
Input array with two stones of different weights	The algorithm should compute the difference and return the result.
Input array with all identical stone weights	The algorithm should repeatedly smash pairs of equal weights until only one or zero stones remain, handling repeated subtractions correctly.
Large input array with widely varying stone weights	Using a max-heap data structure ensures the two heaviest stones are efficiently selected, allowing the solution to scale well.
Extremely large stone weights potentially leading to integer overflow	Use a data type with a larger range (e.g., long) to prevent integer overflow during subtractions.
A sequence of operations resulting in an empty heap or single remaining element	The algorithm needs to correctly iterate until the heap has at most one element, returning 0 for an empty heap or the single element's weight.