Bird
Raised Fist0
Interview Prepdp-knapsackmediumGoogleAmazon

Last Stone Weight II

Choose your preparation mode4 modes available
▶
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.
📊
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.
Step 1/10
·Active fill★Answer cell
Initializing dp array
i\w01234567891011
i=0True???????????
half
Initializing dp array
i\w01234567891011
i=0TrueFalseFalseFalseFalseFalseFalseFalseFalseFalseFalseFalse
dp[0]=True
Item 0 - wt:2 val:0
i\w01234567891011
i=0TrueFalseTrueFalseFalseFalseFalseFalseFalseFalseFalseFalse
dp[2] updated
Item 1 - wt:7 val:0
i\w01234567891011
i=0TrueFalseTrueFalseFalseFalseFalseTrueFalseTrueFalseFalse
dp[7] updated
Item 2 - wt:4 val:0
i\w01234567891011
i=0TrueFalseTrueFalseTrueFalseTrueTrueFalseTrueFalseTrue
dp[4] updated
Item 3 - wt:1 val:0
i\w01234567891011
i=0TrueTrueTrueFalseTrueTrueTrueTrueTrueTrueTrueTrue
dp[1] updated
Item 4 - wt:8 val:0
i\w01234567891011
i=0TrueTrueTrueFalseTrueTrueTrueTrueTrueTrueTrueTrue
dp[8] updated
Item 5 - wt:1 val:0
i\w01234567891011
i=0TrueTrueTrueTrueTrueTrueTrueTrueTrueTrueTrueTrue
dp[3] updated
Item 5 - wt:1 val:0
i\w01234567891011
i=0TrueTrueTrueTrueTrueTrueTrueTrueTrueTrueTrueTrue
answer cell
Item 5 - wt:1 val:0
i\w01234567891011
i=0TrueTrueTrueTrueTrueTrueTrueTrueTrueTrueTrueTrue
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/5)
1. Consider the following code snippet for the coin change problem. What is the value of dp[5] after the outer loop iteration i=5 completes when coins = [1, 2, 5] and amount = 5?
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount]

print(coinChange([1,2,5], 5))
easy
A. 5
B. 2
C. 3
D. 1

Solution

  1. Step 1: Trace dp array updates up to i=5

    dp[0]=0; For i=1: dp[1]=min(inf,1+dp[0])=1; i=2: dp[2]=min(inf,1+dp[1],1+dp[0])=1; i=3: dp[3]=min(inf,1+dp[2],1+dp[1])=2; i=4: dp[4]=min(inf,1+dp[3],1+dp[2])=2; i=5: dp[5]=min(inf,1+dp[4],1+dp[3],1+dp[0])=min(inf,3,3,1)=1
  2. Step 2: Confirm dp[5] value

    Using coin 5 directly gives dp[5]=1, which is minimal.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    dp[5] = 1 coin (coin 5) [OK]
Hint: Direct coin equal to amount sets dp[amount] to 1 [OK]
Common Mistakes:
  • Off-by-one errors in indexing dp
  • Ignoring direct coin match
2. Consider the following Python code implementing the optimal job scheduling solution. What is the value of dp[2] after the loop iteration with i=2 when the input is startTime = [1, 2, 3], endTime = [3, 5, 10], and profit = [20, 20, 100]?
easy
A. 120
B. 20
C. 140
D. 100

Solution

  1. Step 1: Sort jobs by end time

    Jobs sorted by end time: [(1,3,20), (2,5,20), (3,10,100)]. Ends = [3,5,10]
  2. Step 2: Calculate dp[2]

    For i=2 (job with start=3, end=10, profit=100): binary search idx = bisect_right(ends, 2) - 1 = 0 (job 0 compatible). take = 100 + dp[0] = 100 + 20 = 120; skip = dp[1] = max profit till job 1 = 20 (from previous iterations). dp[2] = max(120, 20) = 120.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    dp array after iteration 2 is [20, 20, 120] [OK]
Hint: Binary search finds last compatible job index correctly [OK]
Common Mistakes:
  • Off-by-one in binary search index
  • Using dp[i-1] incorrectly
  • Ignoring base case for dp[0]
3. The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?
def integer_break(n):
    dp = [0] * n
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]
medium
A. Line 3: dp[1] = 1 base case initialization
B. Line 2: dp array size is n instead of n+1
C. Line 5: Outer loop range from 2 to n+1
D. Line 7: Using max(j, dp[j]) instead of just dp[j]

Solution

  1. Step 1: Check dp array size

    dp is initialized with size n, but indices up to n are accessed (dp[i], dp[i-j]) which requires size n+1.
  2. Step 2: Consequences of wrong size

    Accessing dp[n] or dp[i-j] when i=n causes index out of range or incorrect results.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    dp array must be size n+1 to safely index up to n [OK]
Hint: Check array size matches max index accessed [OK]
Common Mistakes:
  • Forgetting dp size off-by-one
  • Misplacing base case initialization
4. What is the time complexity of the bottom-up DP solution with binary search for the minimum cost tickets problem, given n travel days?
medium
A. O(n^2) because for each day we scan all future days
B. O(n log n) because for each day we perform 3 binary searches over the days array
C. O(n) because we only iterate once over the days array
D. O(n * 3 * n) due to nested loops over days and durations

Solution

  1. Step 1: Identify loops and operations

    Outer loop runs n times (for each day). Inner loop runs 3 times (for each ticket duration). Each inner iteration does a binary search (log n) to find next uncovered day.
  2. Step 2: Calculate total complexity

    Total time = n * 3 * log n = O(n log n). Linear scan or nested loops over days would be O(n^2), but binary search reduces it.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Binary search reduces inner loop from O(n) to O(log n) [OK]
Hint: Binary search reduces complexity from quadratic to n log n [OK]
Common Mistakes:
  • Assuming inner loop is linear scan
  • Ignoring binary search effect
  • Confusing space with time complexity
5. Suppose the problem is modified so that you want to find the minimum number of perfect squares summing to n, but now each perfect square can only be used at most once. Which of the following changes correctly adapts the algorithm?
hard
A. Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse
B. Use a top-down memoized recursion with a visited set to avoid reusing squares
C. Use a 2D DP array where dp[i][j] represents minimum squares using first j squares to sum to i
D. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly

Solution

  1. Step 1: Understand the constraint change

    Limiting each perfect square to be used at most once converts the problem from unbounded to 0/1 knapsack variant, requiring tracking which squares are used.
  2. Step 2: Identify correct DP adaptation

    A 2D DP array dp[i][j] that tracks minimum squares to sum to i using first j squares correctly models the usage constraint. Other options either do not prevent reuse or do not track usage properly.
  3. Step 3: Confirm why other options fail

    Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse still allows reuse implicitly. Use a top-down memoized recursion with a visited set to avoid reusing squares is inefficient and complex. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly's order change alone doesn't enforce usage limits.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    0/1 knapsack requires 2D DP to track usage [OK]
Hint: At-most-once usage -> 0/1 knapsack -> 2D DP needed [OK]
Common Mistakes:
  • Trying to reuse unbounded DP
  • Ignoring usage constraints in DP state
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