Last Stone Weight II

▶

Steps

setup

Calculate total sum and half

Compute the total sum of stones (23) and calculate half (11) to limit the DP array size.

💡 Focusing on sums up to half the total is key because the problem reduces to partitioning stones into two groups with minimal difference.

Line:

total = sum(stones)
half = total // 2

💡 The problem transforms into finding a subset of stones with sum as close as possible to half the total.

setup

Initialize DP array with dp[0] = True

Initialize a boolean DP array of size half+1 (12) with dp[0] set to True, meaning sum 0 is always achievable.

💡 Starting with dp[0] = True establishes the base case: zero sum is achievable with no stones.

Line:

dp = [False] * (half + 1)
dp[0] = True

💡 This initialization sets the foundation for building achievable sums incrementally.

fill_cells

Process stone 0 with weight 2

Process the first stone (weight 2), iterating sums backwards from 11 down to 2 to update achievable sums.

💡 Backward iteration prevents using the same stone multiple times in one iteration and updates sums achievable by including this stone.

Line:

for w in range(half, weight - 1, -1):
    dp[w] = dp[w] or dp[w - weight]

💡 dp[2] becomes True because dp[0] was True, meaning sum 2 is now achievable.

fill_cells

Process stone 1 with weight 7

Process the second stone (weight 7), updating dp from 11 down to 7.

💡 Including stone 7 expands achievable sums by adding 7 to previously achievable sums.

Line:

for w in range(half, weight - 1, -1):
    dp[w] = dp[w] or dp[w - weight]

💡 dp[7] and dp[9] become True because dp[0] and dp[2] were True respectively.

fill_cells

Process stone 2 with weight 4

Process the third stone (weight 4), updating dp from 11 down to 4.

💡 Adding stone 4 allows sums that are 4 more than previously achievable sums.

Line:

for w in range(half, weight - 1, -1):
    dp[w] = dp[w] or dp[w - weight]

💡 dp[4], dp[6], and dp[11] become True because dp[0], dp[2], and dp[7] were True respectively.

fill_cells

Process stone 3 with weight 1

Process the fourth stone (weight 1), updating dp from 11 down to 1.

💡 Small stones help fill in gaps in achievable sums, increasing granularity.

Line:

for w in range(half, weight - 1, -1):
    dp[w] = dp[w] or dp[w - weight]

💡 dp[1], dp[5], dp[7], dp[8], and dp[10] become True based on previous dp values.

fill_cells

Process stone 4 with weight 8

Process the fifth stone (weight 8), updating dp from 11 down to 8.

💡 Large stones create new achievable sums by adding to smaller sums.

Line:

for w in range(half, weight - 1, -1):
    dp[w] = dp[w] or dp[w - weight]

💡 dp[8], dp[9], dp[10], and dp[11] remain or become True based on dp[w-8].

fill_cells

Process stone 5 with weight 1

Process the last stone (weight 1), updating dp from 11 down to 1.

💡 This last stone may fill remaining gaps in achievable sums.

Line:

for w in range(half, weight - 1, -1):
    dp[w] = dp[w] or dp[w - weight]

💡 dp[3] becomes True, filling a gap and making all sums from 0 to 11 achievable.

traverse

Find largest achievable sum w ≤ half

Scan dp array backwards from 11 down to 0 to find the largest w where dp[w] is True.

💡 Finding this w gives the closest sum to half the total, minimizing the difference.

Line:

for w in range(half, -1, -1):
    if dp[w]:
        return total - 2 * w

💡 The best partition sum is 11, leading to minimal last stone weight difference.

reconstruct

Return final answer

Return the minimal last stone weight difference, which is 1.

💡 This final step concludes the algorithm by outputting the minimal achievable difference.

Line:

return total - 2 * w

💡 The algorithm successfully finds the minimal last stone weight after optimal smashing.

def lastStoneWeightII(stones):
    total = sum(stones)  # STEP 1
    half = total // 2    # STEP 1
    dp = [False] * (half + 1)  # STEP 2
    dp[0] = True         # STEP 2

    for i, weight in enumerate(stones):  # STEP 3-8
        for w in range(half, weight - 1, -1):
            dp[w] = dp[w] or dp[w - weight]  # update dp

    for w in range(half, -1, -1):  # STEP 9
        if dp[w]:
            return total - 2 * w  # STEP 10

if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))

📊

Last Stone Weight II - Watch the Algorithm Execute, Step by Step

Watching the DP array update step-by-step reveals how the problem reduces to a subset sum variant and how the algorithm efficiently finds the closest sum to half the total.

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	?	?	?	?	?	?	?	?	?	?	?

half

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	False	False	False	False	False	False	False	False	False	False	False

dp[0]=True

Item 0 - wt:2 val:0

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	False	True	False	False	False	False	False	False	False	False	False

dp[2] updated

Item 1 - wt:7 val:0

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	False	True	False	False	False	False	True	False	True	False	False

dp[7] updated

Item 2 - wt:4 val:0

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	False	True	False	True	False	True	True	False	True	False	True

dp[4] updated

Item 3 - wt:1 val:0

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	True	False	True	True	True	True	True	True	True	True

dp[1] updated

Item 4 - wt:8 val:0

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	True	False	True	True	True	True	True	True	True	True

dp[8] updated

Item 5 - wt:1 val:0

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	True	True	True	True	True	True	True	True	True	True

dp[3] updated

Item 5 - wt:1 val:0

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	True	True	True	True	True	True	True	True	True	True

answer cell

Item 5 - wt:1 val:0

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	True	True	True	True	True	True	True	True	True	True

final answer

Key Takeaways

✓ The problem reduces to finding a subset sum closest to half the total sum.

This insight is hard to see from code alone but becomes clear when watching achievable sums build up.

✓ Backward iteration in DP prevents reuse of the same stone multiple times in one iteration.

Visualizing the backward updates clarifies why the order of iteration matters.

✓ The final answer is found by scanning the DP array from half downwards to find the best achievable sum.

Seeing the final scan step highlights how the minimal difference is computed from the DP results.

Practice

1. Given the following code, what is the output when coins = [1, 2, 5] and amount = 5?

def count_ways_space_opt(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    return dp[amount]

coins = [1, 2, 5]
amount = 5
print(count_ways_space_opt(coins, amount))

easy

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Trace dp array updates for each coin

   Start dp = [1,0,0,0,0,0]. After coin=1, dp = [1,1,1,1,1,1]. After coin=2, dp = [1,1,2,2,3,3]. After coin=5, dp = [1,1,2,2,3,6].

2. Step 2: Confirm dp[5] value

   dp[5] = 6, representing 6 ways to make amount 5 with coins [1,2,5].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual dp tracing matches output 6 [OK]

Hint: DP accumulates counts incrementally per coin [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Miscounting after last coin iteration
• Confusing permutations with combinations

2. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that repeatedly picks the largest element and tries to fit it into subsets

B. Dynamic programming with bitmask tabulation that tracks subset sums for all combinations

C. Simple backtracking without memoization that tries all possible assignments

D. Sorting the array and using a two-pointer technique to pair elements

Solution

1. Step 1: Understand problem constraints

   The problem requires partitioning into equal sum subsets, which is a classic NP-complete problem requiring exploration of subsets.

2. Step 2: Identify algorithmic pattern

   Dynamic programming with bitmask tabulation efficiently explores all subsets and tracks partial sums modulo target, guaranteeing optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask DP covers all subsets systematically [OK]

Hint: Bitmask DP tracks all subset sums efficiently [OK]

Common Mistakes:

• Assuming greedy always works for equal sum partition
• Using backtracking without memoization leads to timeouts

3. You need to find the minimum number of perfect square numbers that sum to a given integer n. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming using unbounded knapsack pattern with bottom-up tabulation

B. Greedy approach picking the largest square first until the sum is reached

C. Simple recursion without memoization exploring all combinations

D. Sorting all squares and using binary search to find the closest sum

Solution

1. Step 1: Understand problem constraints

   The problem requires the minimum count of perfect squares summing to n, which is a classic unbounded knapsack variant where items (squares) can be reused.

2. Step 2: Identify algorithm that guarantees optimality

   Greedy fails because picking largest squares first can be suboptimal (e.g., n=12). Simple recursion is correct but inefficient. Binary search does not solve the combinatorial optimization. Bottom-up DP with unbounded knapsack pattern systematically explores all combinations and ensures optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP approach always finds minimum count [OK]

Hint: Greedy fails; DP unbounded knapsack guarantees optimal [OK]

Common Mistakes:

• Assuming greedy works for minimum perfect squares
• Confusing top-down recursion with guaranteed efficiency

4. Consider the following code for computing the minimum number of perfect squares summing to n. What is the value of dp[4] after the outer loop iteration i = 4 completes?

easy

A. 4

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace dp[4] updates

   For i=4, j iterates over 1 and 2 because 1*1=1 <=4 and 2*2=4 <=4. - For j=1: dp[4] = min(inf, 1 + dp[3]) = 1 + dp[3] - For j=2: dp[4] = min(previous, 1 + dp[0]) = min(previous, 1 + 0) = 1 Since dp[0] = 0, dp[4] becomes 1.

2. Step 2: Confirm dp[4] final value

   dp[4] = 1 means 4 can be represented as one perfect square (2*2). This matches the expected minimal count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   dp[4] = 1 for 4 = 2^2 [OK]

Hint: dp[4] = 1 because 4 is a perfect square itself [OK]

Common Mistakes:

• Off-by-one errors in loop
• Ignoring dp[0] base case

5. What is the time complexity of the optimal job scheduling algorithm that sorts jobs by end time and uses binary search with a DP array of size n?

medium

A. O(n log W) where W is the maximum end time

B. O(n^2) due to nested loops over all jobs

C. O(n) because each job is processed once

D. O(n log n) due to sorting and binary searches for each job

Solution

1. Step 1: Identify sorting cost

   Sorting n jobs by end time costs O(n log n).

2. Step 2: Analyze DP loop with binary search

   For each job, binary search among ends array costs O(log n), repeated n times -> O(n log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting + n binary searches dominate; no nested O(n^2) loops [OK]

Hint: Sorting + binary search per job -> O(n log n) [OK]

Common Mistakes:

• Assuming O(n^2) due to DP
• Ignoring binary search cost
• Confusing max end time W with input size n