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
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
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.
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/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
Step 1: Understand job scheduling constraints
The problem requires selecting non-overlapping jobs to maximize profit, which is a classic weighted interval scheduling problem.
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.
Final Answer:
Option A -> Option A
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
Step 1: Understand iteration order effect
Iterating amounts backwards causes dp to count permutations, not combinations.
Step 2: Identify bug line
Line 5 iterates w from amount down to coin, which breaks combination counting logic.
Final Answer:
Option A -> Option A
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
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.
Step 2: Verify loop direction
Though iterating backwards is incorrect for unlimited coin usage, the critical bug causing zero results is dp[0] initialization.
Final Answer:
Option A -> Option A
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
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.
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.
Final Answer:
Option A -> Option A
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
Step 1: Understand reuse impact
Allowing unlimited reuse breaks the uniqueness assumption of subsets represented by bitmasks.