We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Last Stone Weight II

Number: 1130

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of stones where each stone's weight is represented by an integer, we repeatedly take two stones and smash them together. If the stones have equal weight, both are destroyed; otherwise, the lighter stone is completely destroyed, and the heavier stone's new weight becomes the difference between the two. The goal is to compute the minimum possible weight of the remaining stone (or 0 if no stones remain) after performing a series of such operations optimally.

Key Insights

  • The problem can be reinterpreted as a partition problem where we divide the stones into two groups, and the result is the difference between the sums of these two groups.
  • The optimal result is achieved when the difference between the two group sums is minimized.
  • By framing the problem this way, it becomes a variant of the classic subset sum / knapsack problem.
  • Use Dynamic Programming (DP) to find the best achievable subset sum that does not exceed half of the total sum of all stones.

Space and Time Complexity

Time Complexity: O(n * S) where n is the number of stones and S is the total sum of stones. Space Complexity: O(S), where S is the total sum of stones (DP array space).

Solution

We convert the problem into a subset sum problem:

  1. Compute the total sum of the stones.
  2. Use a DP array to record which subset sums are possible.
  3. Iterate through each stone and update the DP array in reverse order to ensure each stone is used only once.
  4. Find the largest subset sum (s1) that does not exceed half of the total sum.
  5. The answer is the difference between the total sum and twice this subset sum (total - 2 * s1), representing the minimum remaining weight.

Code Solutions

# Python solution for Last Stone Weight II

def lastStoneWeightII(stones):
    total_sum = sum(stones)  # Total sum of all stones
    half_sum = total_sum // 2  # Maximum sum we target for one of the groups
    dp = [False] * (half_sum + 1)  # DP array where dp[j] indicates if sum j is achievable
    dp[0] = True  # Base case: sum 0 is always achievable
    
    # Process each stone
    for stone in stones:
        # Traverse backwards to avoid using the same stone twice in one iteration
        for j in range(half_sum, stone - 1, -1):
            if dp[j - stone]:
                dp[j] = True

    # Find the best achievable subset sum (s1) closest to half_sum
    for s1 in range(half_sum, -1, -1):
        if dp[s1]:
            # The minimal possible remaining stone weight
            return total_sum - 2 * s1

    return 0  # Fallback, though this line should never be reached

# Example usage
print(lastStoneWeightII([2,7,4,1,8,1]))  # Expected output: 1
← Back to All Questions