Bird
Raised Fist0
Interview Prepdp-knapsackmediumGoogleAmazon

Last Stone Weight II

Choose your preparation mode4 modes available
🎯
Last Stone Weight II
mediumDPGoogleAmazon

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.

💡 This problem is a classic example of partitioning a set into two subsets to minimize the difference of their sums. Beginners often struggle because it looks like a greedy problem but requires dynamic programming to handle all combinations efficiently.
📋
Problem Statement

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
💡
Example
Input"[2,7,4,1,8,1]"
Output1

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

  • Single stone → output is the stone's weight
  • All stones have the same weight → output is 0
  • Two stones with different weights → output is their absolute difference
  • Large number of stones with small weights → tests efficiency
🔁
Why DP?
Why greedy fails:

Greedy fails because smashing the heaviest stones first does not guarantee minimal last stone weight. For example, stones = [2,7,4,1,8,1], greedy smashing largest stones first leads to suboptimal results.

DP state:

dp[i][w] = True if it is possible to achieve a subset sum w using the first i stones.

Recurrence:dp[i][w] = dp[i-1][w] or dp[i-1][w - stones[i-1]] if w >= stones[i-1]

For each stone, either we don't include it (dp[i-1][w]) or include it if possible (dp[i-1][w - stone weight]).

⚠️
Common Mistakes
Using greedy approach to always smash largest stones first

Leads to incorrect minimal last stone weight

✅ Use DP to consider all subset partitions

Not iterating backwards in space optimized DP

Counts stones multiple times, producing wrong results

✅ Iterate sums from high to low to preserve 0/1 knapsack constraints

Forgetting to initialize dp[0][0] = True in tabulation

No sums are marked achievable, DP fails

✅ Initialize dp[0][0] = True to represent sum zero achievable with zero stones

Using difference as DP state in memoization without normalization

Memo keys become large and inefficient, causing TLE

✅ Use subset sum approach or limit difference range

Not handling edge cases like single stone or all equal stones

Incorrect output or runtime errors

✅ Add checks or rely on DP base cases to handle these

🧠
Brute Force (Pure Recursion)
💡 Brute force helps understand the problem by exploring all possible partitions of stones into two groups, but it is inefficient due to exponential time complexity.

Intuition

Try all ways to assign each stone to one of two piles and compute the minimal difference of their sums.

Algorithm

  1. Define a recursive function that tries placing each stone in either of two subsets.
  2. At each step, recurse with updated sums for both subsets.
  3. When all stones are assigned, compute the absolute difference of sums.
  4. Return the minimal difference found among all assignments.
💡 This approach is conceptually simple but inefficient because it explores all 2^n assignments.
Recurrence:f(i, sum1, sum2) = min(f(i+1, sum1 + stones[i], sum2), f(i+1, sum1, sum2 + stones[i]))
</>
Code
def lastStoneWeightII(stones):
    n = len(stones)
    def dfs(i, sum1, sum2):
        if i == n:
            return abs(sum1 - sum2)
        left = dfs(i + 1, sum1 + stones[i], sum2)
        right = dfs(i + 1, sum1, sum2 + stones[i])
        return min(left, right)

    return dfs(0, 0, 0)

# Driver code
if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))
Line Notes
def dfs(i, sum1, sum2):Defines recursive helper to explore subsets
if i == n:Base case: all stones assigned
return abs(sum1 - sum2)Compute difference when all stones assigned
left = dfs(i + 1, sum1 + stones[i], sum2)Assign current stone to first subset
right = dfs(i + 1, sum1, sum2 + stones[i])Assign current stone to second subset
return min(left, right)Choose minimal difference from both assignments
import java.util.*;
public class Solution {
    public int lastStoneWeightII(int[] stones) {
        return dfs(stones, 0, 0, 0);
    }
    private int dfs(int[] stones, int i, int sum1, int sum2) {
        if (i == stones.length) {
            return Math.abs(sum1 - sum2);
        }
        int left = dfs(stones, i + 1, sum1 + stones[i], sum2);
        int right = dfs(stones, i + 1, sum1, sum2 + stones[i]);
        return Math.min(left, right);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] stones = {2,7,4,1,8,1};
        System.out.println(sol.lastStoneWeightII(stones));
    }
}
Line Notes
public int lastStoneWeightII(int[] stones)Entry point for solution
if (i == stones.length)Base case: all stones assigned
return Math.abs(sum1 - sum2)Calculate difference at leaf
int left = dfs(...)Assign stone to first subset
int right = dfs(...)Assign stone to second subset
return Math.min(left, right)Choose minimal difference
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        return dfs(stones, 0, 0, 0);
    }
private:
    int dfs(vector<int>& stones, int i, int sum1, int sum2) {
        if (i == stones.size()) {
            return abs(sum1 - sum2);
        }
        int left = dfs(stones, i + 1, sum1 + stones[i], sum2);
        int right = dfs(stones, i + 1, sum1, sum2 + stones[i]);
        return min(left, right);
    }
};

int main() {
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};
    cout << sol.lastStoneWeightII(stones) << endl;
    return 0;
}
Line Notes
int dfs(vector<int>& stones, int i, int sum1, int sum2)Recursive helper exploring subsets
if (i == stones.size())Base case: all stones assigned
return abs(sum1 - sum2)Calculate difference at leaf
int left = dfs(...)Assign stone to first subset
int right = dfs(...)Assign stone to second subset
return min(left, right)Choose minimal difference
function lastStoneWeightII(stones) {
    const n = stones.length;
    function dfs(i, sum1, sum2) {
        if (i === n) return Math.abs(sum1 - sum2);
        const left = dfs(i + 1, sum1 + stones[i], sum2);
        const right = dfs(i + 1, sum1, sum2 + stones[i]);
        return Math.min(left, right);
    }
    return dfs(0, 0, 0);
}

// Test
console.log(lastStoneWeightII([2,7,4,1,8,1]));
Line Notes
function dfs(i, sum1, sum2)Recursive helper to explore subsets
if (i === n)Base case: all stones assigned
return Math.abs(sum1 - sum2)Calculate difference at leaf
const left = dfs(...)Assign stone to first subset
const right = dfs(...)Assign stone to second subset
return Math.min(left, right)Choose minimal difference
⏱
Complexity
TimeO(2^n)
SpaceO(n) due to recursion stack

Each stone has two choices, leading to 2^n combinations.

💡 For n=20, this means over a million calls, which is impractical.
Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠
Top-Down Memoization (Recursion + Caching)
💡 Memoization avoids recomputing the same states by caching results, drastically improving efficiency over brute force.

Intuition

Store results of subproblems defined by current index and sum difference to avoid repeated work.

Algorithm

  1. Define a recursive function with parameters for current index and current sum.
  2. Use a dictionary or map to cache results for each (index, sum) pair.
  3. If a state is cached, return it immediately.
  4. Otherwise, recurse by including or excluding the current stone and cache the minimal difference.
💡 Memoization reduces exponential calls to polynomial by remembering results.
Recurrence:f(i, sum) = min(f(i+1, sum + stones[i]), f(i+1, abs(sum - stones[i])))
</>
Code
def lastStoneWeightII(stones):
    from functools import lru_cache
    n = len(stones)

    @lru_cache(None)
    def dfs(i, diff):
        if i == n:
            return diff
        left = dfs(i + 1, diff + stones[i])
        right = dfs(i + 1, abs(diff - stones[i]))
        return min(left, right)

    return dfs(0, 0)

# Driver code
if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))
Line Notes
@lru_cache(None)Caches results of dfs calls to avoid recomputation
def dfs(i, diff):Recursive function with current index and difference
if i == n:Base case: all stones processed
return diffReturn current difference
left = dfs(i + 1, diff + stones[i])Add current stone weight to difference
right = dfs(i + 1, abs(diff - stones[i]))Subtract current stone weight from difference
return min(left, right)Choose minimal difference
import java.util.*;
public class Solution {
    private int[] stones;
    private Map<String, Integer> memo = new HashMap<>();
    public int lastStoneWeightII(int[] stones) {
        this.stones = stones;
        return dfs(0, 0);
    }
    private int dfs(int i, int diff) {
        if (i == stones.length) return diff;
        String key = i + "," + diff;
        if (memo.containsKey(key)) return memo.get(key);
        int left = dfs(i + 1, diff + stones[i]);
        int right = dfs(i + 1, Math.abs(diff - stones[i]));
        int res = Math.min(left, right);
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] stones = {2,7,4,1,8,1};
        System.out.println(sol.lastStoneWeightII(stones));
    }
}
Line Notes
private Map<String, Integer> memoCache for storing computed states
String key = i + "," + diff;Unique key for memoization
if (memo.containsKey(key))Return cached result if available
int left = dfs(...)Add stone weight to difference
int right = dfs(...)Subtract stone weight from difference
memo.put(key, res);Store computed result
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <cmath>
using namespace std;

class Solution {
    vector<int> stones;
    unordered_map<string, int> memo;
public:
    int lastStoneWeightII(vector<int>& stones) {
        this->stones = stones;
        return dfs(0, 0);
    }
private:
    int dfs(int i, int diff) {
        if (i == stones.size()) return diff;
        string key = to_string(i) + "," + to_string(diff);
        if (memo.count(key)) return memo[key];
        int left = dfs(i + 1, diff + stones[i]);
        int right = dfs(i + 1, abs(diff - stones[i]));
        int res = min(left, right);
        memo[key] = res;
        return res;
    }
};

int main() {
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};
    cout << sol.lastStoneWeightII(stones) << endl;
    return 0;
}
Line Notes
unordered_map<string, int> memo;Cache for memoization
string key = to_string(i) + "," + to_string(diff);Unique key for state
if (memo.count(key))Return cached result if exists
int left = dfs(...)Add stone weight to difference
int right = dfs(...)Subtract stone weight from difference
memo[key] = res;Store computed result
function lastStoneWeightII(stones) {
    const n = stones.length;
    const memo = new Map();
    function dfs(i, diff) {
        if (i === n) return diff;
        const key = i + ',' + diff;
        if (memo.has(key)) return memo.get(key);
        const left = dfs(i + 1, diff + stones[i]);
        const right = dfs(i + 1, Math.abs(diff - stones[i]));
        const res = Math.min(left, right);
        memo.set(key, res);
        return res;
    }
    return dfs(0, 0);
}

// Test
console.log(lastStoneWeightII([2,7,4,1,8,1]));
Line Notes
const memo = new Map();Cache for memoization
const key = i + ',' + diff;Unique key for state
if (memo.has(key))Return cached result if exists
const left = dfs(...)Add stone weight to difference
const right = dfs(...)Subtract stone weight from difference
memo.set(key, res);Store computed result
⏱
Complexity
TimeO(n * sum)
SpaceO(n * sum) due to memoization cache and recursion stack

Memoization reduces exponential calls to polynomial by caching states defined by index and difference.

💡 For n=30 and sum=1500, this is feasible with pruning and caching.
Interview Verdict: Accepted

This approach is efficient enough for the problem constraints and is a good intermediate step.

🧠
Bottom-Up Tabulation (0/1 Knapsack DP)
💡 Tabulation builds the solution iteratively, which is often easier to debug and understand than recursion with memoization.

Intuition

Use a boolean DP table to track which subset sums are achievable with the first i stones, then find the closest sum to half the total weight.

Algorithm

  1. Calculate total sum of stones.
  2. Initialize a 2D boolean DP array dp[n+1][total_sum//2 + 1].
  3. dp[i][w] = True if sum w is achievable using first i stones.
  4. Fill dp iteratively using the recurrence relation.
  5. Find the largest w where dp[n][w] is True, then minimal difference is total_sum - 2*w.
💡 This approach systematically builds all achievable sums and finds the best partition.
Recurrence:dp[i][w] = dp[i-1][w] or dp[i-1][w - stones[i-1]] if w >= stones[i-1]
</>
Code
def lastStoneWeightII(stones):
    total = sum(stones)
    n = len(stones)
    half = total // 2
    dp = [[False] * (half + 1) for _ in range(n + 1)]
    dp[0][0] = True

    for i in range(1, n + 1):
        weight = stones[i - 1]
        for w in range(half + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= weight:
                dp[i][w] = dp[i][w] or dp[i - 1][w - weight]

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

# Driver code
if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))
Line Notes
total = sum(stones)Calculate total weight to find half
dp = [[False] * (half + 1) for _ in range(n + 1)]Initialize DP table for sums
dp[0][0] = TrueSum 0 is achievable with 0 stones
for i in range(1, n + 1):Iterate over stones
dp[i][w] = dp[i - 1][w]Exclude current stone
if w >= weight:Check if current stone can be included
dp[i][w] = dp[i][w] or dp[i - 1][w - weight]Include current stone if possible
for w in range(half, -1, -1):Find closest achievable sum to half
import java.util.*;
public class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int s : stones) total += s;
        int n = stones.length;
        int half = total / 2;
        boolean[][] dp = new boolean[n + 1][half + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            int weight = stones[i - 1];
            for (int w = 0; w <= half; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= weight) dp[i][w] = dp[i][w] || dp[i - 1][w - weight];
            }
        }
        for (int w = half; w >= 0; w--) {
            if (dp[n][w]) return total - 2 * w;
        }
        return 0;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] stones = {2,7,4,1,8,1};
        System.out.println(sol.lastStoneWeightII(stones));
    }
}
Line Notes
int total = 0;Calculate total weight
boolean[][] dp = new boolean[n + 1][half + 1];DP table for achievable sums
dp[0][0] = true;Sum 0 achievable with 0 stones
for (int i = 1; i <= n; i++)Iterate stones
dp[i][w] = dp[i - 1][w];Exclude current stone
if (w >= weight)Check if stone can be included
dp[i][w] = dp[i][w] || dp[i - 1][w - weight];Include stone if possible
for (int w = half; w >= 0; w--)Find closest sum to half
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int total = 0;
        for (int s : stones) total += s;
        int n = stones.size();
        int half = total / 2;
        vector<vector<bool>> dp(n + 1, vector<bool>(half + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            int weight = stones[i - 1];
            for (int w = 0; w <= half; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= weight) dp[i][w] = dp[i][w] || dp[i - 1][w - weight];
            }
        }
        for (int w = half; w >= 0; w--) {
            if (dp[n][w]) return total - 2 * w;
        }
        return 0;
    }
};

int main() {
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};
    cout << sol.lastStoneWeightII(stones) << endl;
    return 0;
}
Line Notes
int total = 0;Calculate total weight
vector<vector<bool>> dp(n + 1, vector<bool>(half + 1, false));DP table for sums
dp[0][0] = true;Sum 0 achievable with no stones
for (int i = 1; i <= n; i++)Iterate stones
dp[i][w] = dp[i - 1][w];Exclude current stone
if (w >= weight)Check if stone can be included
dp[i][w] = dp[i][w] || dp[i - 1][w - weight];Include stone if possible
for (int w = half; w >= 0; w--)Find closest sum to half
function lastStoneWeightII(stones) {
    const total = stones.reduce((a, b) => a + b, 0);
    const n = stones.length;
    const half = Math.floor(total / 2);
    const dp = Array.from({ length: n + 1 }, () => Array(half + 1).fill(false));
    dp[0][0] = true;

    for (let i = 1; i <= n; i++) {
        const weight = stones[i - 1];
        for (let w = 0; w <= half; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weight) dp[i][w] = dp[i][w] || dp[i - 1][w - weight];
        }
    }

    for (let w = half; w >= 0; w--) {
        if (dp[n][w]) return total - 2 * w;
    }
    return 0;
}

// Test
console.log(lastStoneWeightII([2,7,4,1,8,1]));
Line Notes
const total = stones.reduce((a, b) => a + b, 0);Calculate total weight
const dp = Array.from({ length: n + 1 }, () => Array(half + 1).fill(false));DP table for sums
dp[0][0] = true;Sum 0 achievable with no stones
for (let i = 1; i <= n; i++)Iterate stones
dp[i][w] = dp[i - 1][w];Exclude current stone
if (w >= weight)Check if stone can be included
dp[i][w] = dp[i][w] || dp[i - 1][w - weight];Include stone if possible
for (let w = half; w >= 0; w--)Find closest sum to half
⏱
Complexity
TimeO(n * sum)
SpaceO(n * sum)

We fill a DP table with n rows and sum/2 columns.

💡 For n=30 and sum=1500, this is efficient and practical.
Interview Verdict: Accepted

This is the standard optimal DP solution for this problem.

🧠
Space Optimized Bottom-Up DP (1D Array)
💡 We can reduce space from O(n*sum) to O(sum) by using a 1D DP array and iterating backwards over sums.

Intuition

Track achievable sums with a single array, updating from high to low to avoid reuse of stones in the same iteration.

Algorithm

  1. Calculate total sum and half.
  2. Initialize a 1D boolean dp array of size half+1 with dp[0] = True.
  3. For each stone, iterate sums backwards from half to stone weight.
  4. Update dp[w] |= dp[w - stone] to mark achievable sums.
  5. Find the largest w where dp[w] is True and return total - 2*w.
💡 Backward iteration ensures stones are counted once per iteration, preserving 0/1 knapsack constraints.
Recurrence:dp[w] = dp[w] or dp[w - stones[i]] if w >= stones[i]
</>
Code
def lastStoneWeightII(stones):
    total = sum(stones)
    half = total // 2
    dp = [False] * (half + 1)
    dp[0] = True

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

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

# Driver code
if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))
Line Notes
dp = [False] * (half + 1)Initialize 1D DP array for sums
dp[0] = TrueSum 0 achievable with no stones
for w in range(half, weight - 1, -1)Iterate backwards to avoid reuse
dp[w] = dp[w] or dp[w - weight]Update achievable sums including current stone
for w in range(half, -1, -1)Find closest achievable sum to half
import java.util.*;
public class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int s : stones) total += s;
        int half = total / 2;
        boolean[] dp = new boolean[half + 1];
        dp[0] = true;
        for (int weight : stones) {
            for (int w = half; w >= weight; w--) {
                dp[w] = dp[w] || dp[w - weight];
            }
        }
        for (int w = half; w >= 0; w--) {
            if (dp[w]) return total - 2 * w;
        }
        return 0;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] stones = {2,7,4,1,8,1};
        System.out.println(sol.lastStoneWeightII(stones));
    }
}
Line Notes
boolean[] dp = new boolean[half + 1];1D DP array for sums
dp[0] = true;Sum 0 achievable with no stones
for (int w = half; w >= weight; w--)Backward iteration to avoid reuse
dp[w] = dp[w] || dp[w - weight];Update achievable sums
for (int w = half; w >= 0; w--)Find closest sum to half
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int total = 0;
        for (int s : stones) total += s;
        int half = total / 2;
        vector<bool> dp(half + 1, false);
        dp[0] = true;
        for (int weight : stones) {
            for (int w = half; w >= weight; w--) {
                dp[w] = dp[w] || dp[w - weight];
            }
        }
        for (int w = half; w >= 0; w--) {
            if (dp[w]) return total - 2 * w;
        }
        return 0;
    }
};

int main() {
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};
    cout << sol.lastStoneWeightII(stones) << endl;
    return 0;
}
Line Notes
vector<bool> dp(half + 1, false);1D DP array for sums
dp[0] = true;Sum 0 achievable with no stones
for (int w = half; w >= weight; w--)Backward iteration to avoid reuse
dp[w] = dp[w] || dp[w - weight];Update achievable sums
for (int w = half; w >= 0; w--)Find closest sum to half
function lastStoneWeightII(stones) {
    const total = stones.reduce((a, b) => a + b, 0);
    const half = Math.floor(total / 2);
    const dp = new Array(half + 1).fill(false);
    dp[0] = true;

    for (const weight of stones) {
        for (let w = half; w >= weight; w--) {
            dp[w] = dp[w] || dp[w - weight];
        }
    }

    for (let w = half; w >= 0; w--) {
        if (dp[w]) return total - 2 * w;
    }
    return 0;
}

// Test
console.log(lastStoneWeightII([2,7,4,1,8,1]));
Line Notes
const dp = new Array(half + 1).fill(false);1D DP array for sums
dp[0] = true;Sum 0 achievable with no stones
for (let w = half; w >= weight; w--)Backward iteration to avoid reuse
dp[w] = dp[w] || dp[w - weight];Update achievable sums
for (let w = half; w >= 0; w--)Find closest sum to half
⏱
Complexity
TimeO(n * sum)
SpaceO(sum)

We use a single DP array of size sum/2 and update it for each stone.

💡 This is the most space-efficient DP solution practical for interviews.
Interview Verdict: Accepted

This is the best practical solution balancing time and space.

📊
All Approaches - One-Glance Tradeoffs
💡 Use space optimized DP in 95% of interviews for best balance of clarity and efficiency.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYesYesMention only - never code
2. Top-Down MemoizationO(n * sum)O(n * sum)Possible but less likelyYesGood intermediate solution
3. Bottom-Up TabulationO(n * sum)O(n * sum)NoYesOptimal DP solution
4. Space Optimized DPO(n * sum)O(sum)NoHarder but possibleBest practical solution
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly.

How to Present

Clarify problem constraints and examples.Explain brute force to show understanding of problem structure.Introduce memoization to optimize brute force.Present bottom-up DP as optimal solution.Mention space optimization if time permits.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of subset sum and partitioning, ability to optimize brute force with DP, and coding skills for DP tabulation.

Common Follow-ups

  • What if stones array is very large? → Use space optimized DP or approximate algorithms.
  • Can you reconstruct the subsets? → Yes, by tracking choices in DP table.
💡 These follow-ups test deeper understanding and ability to extend solutions.
🔍
Pattern Recognition

When to Use

1) Problem involves partitioning or subset sums; 2) Minimize difference between two groups; 3) 0/1 knapsack style constraints; 4) Need to consider all subsets.

Signature Phrases

'partition stones into two groups''minimize the weight difference''subset sum closest to half'

NOT This Pattern When

Greedy or sorting based problems that do not require subset sum or DP.

Similar Problems

Partition Equal Subset Sum - same subset sum DP approachTarget Sum - similar DP with sign assignmentsMinimum Subset Sum Difference - direct minimization of subset difference

Practice

(1/5)
1. Consider the following code for integer break. What is the value of dp[3] after the outer loop iteration i = 3 completes?
def integer_break(n):
    dp = [0] * (n + 1)
    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]

print(integer_break(4))  # Output not asked here
easy
A. 2
B. 4
C. 3
D. 1

Solution

  1. Step 1: Trace dp for i=2

    dp[1] = 1 (given). For i=2, j=1: max_product = max(0, max(1,1)*max(1,1)) = 1, so dp[2] = 1.
  2. Step 2: Trace dp for i=3

    j=1: max_product = max(0, max(1,1)*max(2,dp[2])) = max(0,1*2) = 2 j=2: max_product = max(2, max(2,dp[2])*max(1,dp[1])) = max(2,2*1) = 2 So dp[3] = 2.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    dp[3] = 2 matches manual calculation [OK]
Hint: Trace inner loop carefully for each j [OK]
Common Mistakes:
  • Off-by-one in loop bounds
  • Confusing dp[i-j] with dp[j]
2. Consider the following Python function implementing the Target Sum problem using bottom-up DP with offset indexing. What is the returned value when calling findTargetSumWays([1, 2], 1)?
easy
A. 1
B. 3
C. 0
D. 2

Solution

  1. Step 1: Trace initial dp array

    total=3, offset=3, dp=[0,0,0,1,0,0,0] (index 3 corresponds to sum 0)
  2. Step 2: Process num=1 and num=2 updating dp

    After num=1, dp counts ways to reach sums -1 and 1. After num=2, dp counts ways to reach sums -3,-1,1,3. dp[target+offset]=dp[1+3]=dp[4]=2.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Two ways: +1-2 and -1+2 sum to 1 [OK]
Hint: Offset indexing maps sums to dp indices [OK]
Common Mistakes:
  • Off-by-one errors in indexing dp array
3. 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
4. The following code attempts to solve the job scheduling problem optimally. Which line contains a subtle bug that can cause incorrect results?
medium
A. Line 11: Using bisect_right to find compatible job index
B. Line 7: Creating ends array from job end times
C. Line 4: Sorting jobs by start time instead of end time
D. Line 14: Calculating dp[i] as max of take and skip

Solution

  1. Step 1: Identify sorting criteria

    Jobs must be sorted by end time for binary search on ends array to work correctly.
  2. Step 2: Check sorting line

    Line 4 sorts by start time, breaking DP dependencies and binary search correctness.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting by start time causes incorrect compatible job lookups and suboptimal profits [OK]
Hint: Sort jobs by end time, not start time [OK]
Common Mistakes:
  • Sorting by start time
  • Incorrect binary search bounds
  • Ignoring dp base cases
5. Suppose the coin change problem is modified so that each coin can only be used at most once (0/1 knapsack variant). Which of the following changes to the bottom-up DP approach correctly solves this variant?
hard
A. Use a 2D dp array where dp[i][j] represents minimum coins to make amount j using first i coins, iterating coins outer and amounts inner
B. Sort coins and greedily pick largest coins without repetition until amount is reached
C. Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage)
D. Use the same 1D dp but iterate amounts outer and coins inner, updating dp[j] only if dp[j - coin] was from previous iteration

Solution

  1. Step 1: Understand the 0/1 usage constraint

    Each coin can be used once, so we must track usage per coin, requiring 2D dp.
  2. Step 2: Identify correct DP structure

    2D dp with dp[i][j] = min coins to make j using first i coins ensures no reuse; iterate coins outer, amounts inner.
  3. Step 3: Why other options fail

    Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage) allows unlimited reuse; B is greedy and incorrect; D misuses 1D dp which is for unbounded usage.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    0/1 knapsack requires 2D dp to track coin usage [OK]
Hint: 0/1 knapsack needs 2D dp to prevent reuse [OK]
Common Mistakes:
  • Using unbounded knapsack DP for 0/1 problem
  • Assuming greedy works for minimum coins
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