Last Stone Weight II

📋

Problem

Imagine you have a collection of stones with different weights. You want to smash them together in pairs to minimize the weight of the last remaining stone.

Given an array stones where stones[i] is the weight of the ith stone, you smash stones together. Each smash combines two stones with weights x and y, resulting in either no stone if x == y or a new stone with weight |x - y| if x != y. Return the smallest possible weight of the last stone (or 0 if none remain) after smashing the stones optimally.

1 ≤ stones.length ≤ 301 ≤ stones[i] ≤ 100

Edge cases: Single stone → output is the stone's weightAll stones have the same weight → output is 0Two stones with different weights → output is their absolute difference

</>

IDE

def lastStoneWeightII(stones: list[int]) -> int:public int lastStoneWeightII(int[] stones)int lastStoneWeightII(vector<int>& stones)function lastStoneWeightII(stones)

def lastStoneWeightII(stones):
    # Write your solution here
    pass

class Solution {
    public int lastStoneWeightII(int[] stones) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int lastStoneWeightII(vector<int>& stones) {
    // Write your solution here
    return 0;
}

function lastStoneWeightII(stones) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Always returning 0 without computing subset sums, ignoring actual stone weights.✅ Implement DP to track achievable subset sums and compute minimal difference accordingly.

Wrong: sum of stonesReturning total sum instead of minimal difference, misunderstanding problem requirement.✅ Calculate minimal difference as total sum minus twice the closest subset sum to half total.

Wrong: Incorrect minimal difference due to greedy approachUsing greedy method to pick stones instead of DP subset sum approach.✅ Use DP to explore all subset sums rather than greedy selection.

Wrong: Incorrect minimal difference due to unbounded knapsack logicAllowing reuse of stones multiple times instead of 0/1 knapsack constraint.✅ Ensure DP state tracks item index and does not reuse stones.

Wrong: Timeout or no outputUsing brute force exponential recursion without memoization or DP.✅ Implement DP with O(n*sum) complexity to avoid TLE.

✓

Test Cases

Focus on handling small inputs and base cases correctly before moving on.

Review your DP implementation for common pitfalls like greedy traps and 0/1 vs unbounded confusion.

Ensure your solution is efficient enough to handle the largest inputs within time limits.

t1_01basic

Input{"stones":[2,7,4,1,8,1]}

Expected1

⏱ Performance - must finish in 2000ms

One optimal sequence leads to a last stone weight of 1.

💡 Think about partitioning stones into two groups with minimum difference.

💡 Use 0/1 knapsack to find subset sums close to half the total weight.

💡 Find max subset sum <= total//2, answer is total - 2 * subset_sum.

Why it failed: Incorrect output means subset sum calculation or difference minimization is wrong. Fix by ensuring dp tracks achievable sums correctly.

✓ Correct minimal last stone weight computed.

t1_02basic

Input{"stones":[1,2,3,4,5]}

Expected1

⏱ Performance - must finish in 2000ms

Partition into [1,2,4] and [3,5] with sums 7 and 8, difference 1 is minimal; but better partition is [1,2,3,4] and [5] sums 10 and 5 difference 5 is not minimal; minimal difference is 0 by [1,2,3,4] and [5] is incorrect, correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; correct minimal difference is 0 by [1,2,3,4] and [5] is wrong; minimal difference is 0 by [1,2,3,4] and [5] is wrong; minimal difference is 0 by [1,2,3,4] and [5] is wrong; minimal difference is 0 by [1,2,3,4] and [5] is wrong; minimal difference is 0 by [1,2,3,4] and [5] is wrong; minimal difference is 0 by [1,2,3,4] and [5] is wrong; minimal difference is 0 by [1,2,3,4] and [5] is wrong; minimal difference is 0 by [1,2,3,4] and [5] is wrong; minimal difference is 0 by [1,2,4] and [3,5].

💡 Try to find subsets with sums close to half total weight (15/2=7).

💡 Use DP to check which sums are achievable from stones.

💡 Minimal difference is total - 2 * max achievable sum <= total//2.

Why it failed: Wrong output indicates failure to find correct subset sums or incorrect difference calculation. Fix dp to correctly track achievable sums.

✓ Correct minimal difference found for given stones.

t2_01edge

Input{"stones":[1]}

Expected1

⏱ Performance - must finish in 2000ms

Single stone remains as is, so minimal last stone weight equals stone weight.

💡 Check behavior when only one stone is present.

💡 DP should handle base case with single element correctly.

💡 Return stone weight directly if only one stone.

Why it failed: Output 0 or other value means base case for single stone is mishandled. Fix by returning stone weight when stones length is 1.

✓ Correctly returns single stone weight.

t2_02edge

Input{"stones":[5,5,5,5]}

Expected0

⏱ Performance - must finish in 2000ms

All stones identical; can be paired and smashed to zero weight.

💡 Consider if stones can be partitioned into two equal sum subsets.

💡 DP should find subset sum equal to half total weight.

💡 If total sum is even and subset sum equals half, answer is 0.

Why it failed: Output non-zero means failure to detect perfect partition. Fix dp to correctly identify subset sums equal to half total.

✓ Correctly identifies zero minimal last stone weight.

t2_03edge

Input{"stones":[10,1]}

Expected9

⏱ Performance - must finish in 2000ms

Two stones with different weights, minimal last stone weight is their absolute difference.

💡 For two stones, minimal last stone weight is abs difference.

💡 DP should handle small input correctly.

💡 Check that dp does not overcomplicate two-element cases.

Why it failed: Output other than 9 means incorrect handling of small input or difference calculation. Fix by ensuring dp handles small n correctly.

✓ Correct minimal difference for two stones.

t3_01corner

Input{"stones":[1,2,2,3,4]}

Expected0

⏱ Performance - must finish in 2000ms

Greedy approach fails here; optimal partition yields zero difference.

💡 Greedy picking largest stones first may not yield minimal difference.

💡 Use DP to explore all subset sums rather than greedy.

💡 Check all subset sums to find perfect partition with zero difference.

Why it failed: Output non-zero means greedy approach used incorrectly. Fix by implementing full DP subset sum approach.

✓ DP correctly finds zero difference, avoiding greedy trap.

t3_02corner

Input{"stones":[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]}

Expected0

⏱ Performance - must finish in 2000ms

All stones identical and maximum length; tests 0/1 knapsack correctness and no unbounded confusion.

💡 Ensure each stone is used at most once (0/1 knapsack).

💡 Avoid treating stones as unlimited supply (unbounded knapsack).

💡 DP state must track item index to prevent reuse.

Why it failed: Output non-zero means unbounded knapsack logic used incorrectly. Fix by enforcing 0/1 knapsack constraints in DP.

✓ Correctly applies 0/1 knapsack logic for all identical stones.

t3_03corner

Input{"stones":[100,1,1,1,1]}

Expected96

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in DP indexing and sum calculations.

💡 Check DP indexing carefully to avoid off-by-one errors.

💡 Verify sums and subset sums are computed correctly.

💡 Ensure dp array size matches total sum + 1.

Why it failed: Output other than 97 indicates off-by-one or indexing bug. Fix DP loops and indexing to cover full sum range.

✓ DP indexing and sum calculations are correct.

t4_01performance

Input{"stones":[100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70]}

Expectednull

⏱ Performance - must finish in 2000ms

n=31 stones with large weights; O(n*sum) DP must complete within 2 seconds.

💡 DP complexity is O(n * total_sum), optimize space if needed.

💡 Use bitset or boolean arrays to speed subset sum computations.

💡 Avoid exponential brute force to prevent TLE.

Why it failed: TLE indicates exponential brute force used. Fix by implementing DP with O(n*sum) complexity.

✓ DP solution runs within time limits confirming O(n*sum) complexity.

Practice

1. Consider the following Python code for the Equal Partition problem. What is the value of dp[target] after processing the input [1, 5, 11, 5]?

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for w in range(target, num - 1, -1):
            dp[w] = dp[w] or dp[w - num]

    return dp[target]

print(canPartition([1,5,11,5]))

easy

A. true

B. false

C. null (error occurs)

D. Depends on order of iteration

Solution

1. Step 1: Calculate total and target

   The total sum is 1 + 5 + 11 + 5 = 22, which is even, so target = 11.

2. Step 2: Trace dp array updates for each num

   After processing all nums, dp[11] becomes True because subset {11} or {5,5,1} sums to 11.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Input is classic example where partition exists; dp[target] is True [OK]

Hint: Sum is even and dp[target] tracks subset sums [OK]

Common Mistakes:

• Confusing dp[target] with dp[target-1]
• Forgetting to iterate backwards in dp update

2. You need to find the number of distinct ways to make a target amount using unlimited supply of given coin denominations. Which algorithmic approach guarantees counting all unique combinations without overcounting permutations?

easy

A. Greedy algorithm that picks the largest coin first until the amount is reached

B. Dynamic programming using a 1D array iterating coins first, then amounts

C. Backtracking exploring all permutations of coins to sum to the amount

D. Sorting coins and using two pointers to find pairs that sum to the amount

Solution

1. Step 1: Understand problem constraints

   The problem requires counting unique combinations, not permutations, of coins to reach the target amount.

2. Step 2: Identify algorithm that counts combinations without duplicates

   Dynamic programming iterating coins first ensures each coin is considered in order, avoiding counting permutations multiple times. The 1D DP approach efficiently accumulates counts for each amount.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP with coin-first iteration counts combinations correctly [OK]

Hint: Coin-first DP avoids permutation overcounting [OK]

Common Mistakes:

• Using greedy misses some combinations
• Counting permutations instead of combinations
• Using two pointers only works for pair sums

3. The following code attempts to implement the space-optimized 0/1 Knapsack solution. Identify the line that contains a subtle bug that can cause incorrect results.

def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # Note: iterating forwards
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

medium

A. Line 5: Inner loop iterating forwards over weights.

B. Line 4: Outer loop iterating over items.

C. Line 2: Initializing dp array with zeros.

D. Line 6: Updating dp[w] with max of current and new value.

Solution

1. Step 1: Analyze iteration order in inner loop

   The inner loop iterates forwards from weights[i] to W, which causes the current item to be counted multiple times in the same iteration, violating 0/1 knapsack constraints.

2. Step 2: Correct iteration direction

   Iterating backwards (from W down to weights[i]) ensures each item is only counted once per capacity, preserving correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration causes overcounting items [OK]

Hint: Inner loop must iterate backwards to avoid overcounting [OK]

Common Mistakes:

• Iterating forwards in dp array updates for 0/1 knapsack.

4. What is the time complexity of the DP with bitmask tabulation approach for partitioning an array of size n into k equal sum subsets, where the algorithm iterates over all subsets and elements?

medium

A. O(k^n) because it tries all assignments of elements to k buckets

B. O(n * 2^n) because it iterates over all subsets and elements

C. O(n * target) where target is the subset sum

D. O(2^n * n^2) due to nested loops over subsets and elements

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop iterates over all subsets (2^n), inner loop over n elements.

2. Step 2: Calculate total complexity

   Combining loops gives O(n * 2^n). The target sum does not affect iteration count directly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP bitmask iterates all subsets and elements [OK]

Hint: Bitmask DP complexity is n times 2^n subsets [OK]

Common Mistakes:

• Confusing brute force backtracking complexity with DP complexity
• Assuming complexity depends on target sum

5. The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line 3: Missing base case assignment dp[0] = 0

B. Line 2: dp initialization with infinity

C. Line 5: Outer loop from 1 to n

D. Line 7: Inner loop condition j*j <= i

Solution

1. Step 1: Identify base case importance

   dp[0] = 0 is critical because it represents zero squares needed to sum to zero. Without it, dp[0] remains infinity, causing dp[i] updates to use invalid values.

2. Step 2: Analyze impact of missing dp[0] = 0

   Since dp[0] is infinity, expressions like 1 + dp[i - j*j] become infinity, preventing dp[i] from ever updating correctly, leading to infinite loops or wrong results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dp[0] base case breaks DP initialization [OK]

Hint: dp[0] must be zero to start DP correctly [OK]

Common Mistakes:

• Forgetting dp[0] initialization
• Misplacing loop boundaries