Bird
Raised Fist0
Interview Prepdp-knapsackmediumGoogleAmazon

Last Stone Weight II

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"stones":[2,7,4,1,8,1]}
Expected1

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

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

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].

t2_01edge
Input{"stones":[1]}
Expected1

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

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

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

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

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

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

Greedy approach fails here; optimal partition yields zero difference.

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

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

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

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

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]}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. You are given a list of jobs where each job has a start time, an end time, and a profit. You want to schedule jobs to maximize total profit such that no two jobs overlap. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Dynamic programming with jobs sorted by end time and binary search to find compatible jobs
B. Pure brute force recursion checking all subsets of jobs
C. Greedy algorithm that always picks the job with the earliest end time
D. Dynamic programming based on sorting jobs by start time and using prefix sums

Solution

  1. Step 1: Understand job scheduling constraints

    The problem requires selecting non-overlapping jobs to maximize profit, which is a classic weighted interval scheduling problem.
  2. Step 2: Identify the optimal approach

    Sorting jobs by end time allows binary searching for the last compatible job, enabling a DP solution that builds optimal profit incrementally.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Greedy fails on overlapping jobs with higher profit; DP with binary search handles all cases optimally [OK]
Hint: Sort by end time and use DP with binary search [OK]
Common Mistakes:
  • Assuming greedy by earliest end time always works
  • Sorting by start time only
  • Trying brute force without pruning
2. The following code attempts to count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?
medium
A. Line 5: inner loop iterating backwards over amounts
B. Line 4: outer loop over coins
C. Line 2: dp initialization
D. Line 6: updating dp[w] with dp[w - coin]

Solution

  1. Step 1: Understand iteration order effect

    Iterating amounts backwards causes dp to count permutations, not combinations.
  2. Step 2: Identify bug line

    Line 5 iterates w from amount down to coin, which breaks combination counting logic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Forward iteration over amounts is required to count combinations correctly [OK]
Hint: Check direction of inner loop iteration [OK]
Common Mistakes:
  • Using backward iteration in 1D dp
  • Misplacing dp[0] initialization
3. Identify the bug in the following code snippet for counting ways to make change using 1D DP:
def count_ways_bug(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for w in range(amount, coin - 1, -1):
            dp[w] += dp[w - coin]
    return dp[amount]
What is the bug?
medium
A. dp[0] should be initialized to 1, not 0
B. The inner loop should iterate forwards from coin to amount, not backwards
C. The dp array size should be amount, not amount + 1
D. The return statement should return dp[0] instead of dp[amount]

Solution

  1. Step 1: Check base case initialization

    dp[0] represents ways to make amount 0, which must be 1 (empty combination), but here it is set to 0, causing all dp values to remain 0.
  2. Step 2: Verify loop direction

    Though iterating backwards is incorrect for unlimited coin usage, the critical bug causing zero results is dp[0] initialization.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Correct base case dp[0]=1 is essential for counting ways [OK]
Hint: dp[0] must be 1 to count empty combination [OK]
Common Mistakes:
  • Initializing dp[0] to 0 misses base case
  • Iterating amounts backwards in 1D DP misses combinations
  • Incorrect dp array size causes index errors
4. 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
5. Suppose the problem is modified so that each element in the array can be used multiple times (unlimited reuse) to form k equal sum subsets. Which of the following modifications to the DP with bitmask tabulation approach correctly adapts to this change?
hard
A. Use backtracking with memoization on subsets but do not use bitmasking since reuse breaks subset uniqueness
B. Keep the same bitmask DP but allow setting dp[next_mask] multiple times without restriction
C. Replace bitmask DP with a classic unbounded knapsack DP that tracks sums without bitmasking
D. Modify the bitmask DP to reset dp states after each full subset sum is reached to allow reuse

Solution

  1. Step 1: Understand reuse impact

    Allowing unlimited reuse breaks the uniqueness assumption of subsets represented by bitmasks.
  2. Step 2: Identify suitable DP approach

    Classic unbounded knapsack DP tracks sums without bitmasking, correctly handling reuse.
  3. Step 3: Evaluate other options

    Bitmask DP relies on unique element usage; modifying it without removing bitmasking leads to incorrect states.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Unbounded knapsack DP handles reuse correctly [OK]
Hint: Bitmask DP assumes unique usage; reuse needs unbounded knapsack DP [OK]
Common Mistakes:
  • Trying to reuse bitmask DP without removing uniqueness assumption
  • Ignoring that reuse breaks subset partitioning logic
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard