</> MAANG.io
Sign in
Level101201301
coding interview · 101

Foundations

Master coding interviews with comprehensive coverage of data structures, algorithms, and problem-solving techniques. Progress from fundamentals to advanced topics with expertly curated content.

0/255 solved 0% complete

Knapsack & Subset Thinking

What is this?

Knapsack-style DP is about choosing a subset of items to get the best value while staying under some limit — for each item you decide "take it or leave it," and you reuse the best answers for smaller limits instead of re-trying every combination. Imagine packing a bag with a weight cap and wanting the most value inside. The second, sharper lesson here is that some problems only look like knapsack and actually fold down to a one-line counting observation, so it pays to look before you build a whole table.

flowchart TD A["Items and a capacity"] --> B["For each item take it or leave it"] B --> C["Reuse the best smaller-capacity answer"] C --> D["But first check for a counting shortcut"]

💡 Fun fact: The 0/1 knapsack problem is NP-hard in general, yet the table-filling DP solves it quickly when the capacity is a modest whole number — a famous case where a problem is "hard" in theory but tame for the sizes interviewers actually ask about.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

Core idea: Knapsack-style problems ask you to choose a subset of items to optimize a value under a capacity/constraint — the home of the classic "take it or leave it" DP. But this bucket carries a second, sharper lesson: some problems look like knapsack/DP and actually collapse to a one-line counting insight. Always check for the shortcut before building a table.

Take-it-or-leave-it, and the shortcut

0/1 knapsack take-it-or-leave-it recurrence dp[i][w] = max(skip item i, take item i + dp[i-1][w - wt]), with the reminder to first ask whether structure makes the heavy DP unnecessary

Recognizing structure (equal values move in lockstep, a quantity is just a count of distinct levels) can replace an O(n·W) table with an O(n) observation. The skill is knowing which situation you're in.

The problem

Knapsack / subset thinking bucket pointing to its problem: Make Array Zero by Subtracting Equal Amounts

  • Make Array Zero by Subtracting Equal Amounts — filed under knapsack/DP, but the answer is simply the number of distinct nonzero values (each operation peels one level). A clean example of beating a heavy DP framing with a counting insight.

The full 0/1 and unbounded knapsack DPs (subset-sum, partition, bounded coin variants) build directly on the take-it-or-leave-it recurrence and the unbounded version you met in Coin Change.

Key takeaways

  • Knapsack = choose a subset under a constraint, via a take-it-or-leave-it recurrence.
  • Check for a counting/greedy shortcut first — not everything filed as DP needs a table.
  • Structure beats brute — equal/lockstep values and "distinct levels" often collapse the problem.
  • Why interviewers love it: they want to see whether you reach for the right tool, not the heaviest one.

Problem: Make Array Zero by Subtracting Equal Amounts.

Core idea: every operation subtracts the same amount from every nonzero element, so all elements that currently share a value stay tied together forever. Each operation can wipe out exactly one distinct nonzero value level. The minimum number of operations is therefore just the count of distinct nonzero values — len(set(v for v in nums if v != 0)). No table, no DP.

Problem, rephrased

You're given an array nums of non-negative integers. In one operation you:

  1. pick a positive number x that is at most the smallest nonzero element currently in the array, then
  2. subtract x from every nonzero element (zeros are left alone).

Return the minimum number of operations needed to make every element 0.

Picture the values as stacks of blocks of different heights. Each operation slices a flat horizontal layer of height x off the bottom of all the nonzero stacks at once. Stacks that have already hit the floor (value 0) are skipped. You want to flatten everything to the ground in as few slices as possible.

nums Distinct nonzero values Answer (min ops)
[1,5,0,3,5] {1, 3, 5} 3
[0] {} 0
[2,2,2] {2} 1
[4,1,7,1,4] {1, 4, 7} 3
[0,0,0] {} 0

Notice the third row: three equal stacks need just one slice, because they're all at the same level. And the first and fourth rows: duplicate values (5 appears twice, 1 and 4 each appear twice) don't add work — once you flatten a level, every stack sitting at that level drops together.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.