Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Maximise the COUNT of toys, not the money spent. Sort prices ascending, then walk left to right buying each toy while the running total stays within budget — the moment a toy would overshoot, stop. Sorting dominates at O(n log n); the buying scan is O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you spot that maximising COUNT (not value) collapses the problem to 'buy the cheapest things first', and whether you can justify the greedy choice instead of guessing.
Where candidates slip
Trying to maximise money spent or reaching for knapsack DP — over-engineering a problem where every toy has equal value, so greedy is provably optimal.
How to stand out
Give the one-line exchange argument: swapping a chosen expensive toy for an unchosen cheaper one never decreases the count and never increases spend, so the cheapest-first prefix is optimal.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewBuy the most ITEMS under a budgetDo items differ in value?YesNo, only cost mattersExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Try Every Subset
1Hint 1Explore hintHide hint
The answer is some subset of toys whose total cost is ≤ k. How many subsets are there, and could you check them all?
2Hint 2Explore hintHide hint
For each of the 2ⁿ subsets, sum its prices; if the sum is within budget, record its size. Keep the largest size seen.
3Hint 3Explore hintHide hint
This is correct but explodes — with n = 10⁵ there are far more subsets than atoms in the universe. Use it only to motivate something smarter.
A · Core idea
The most literal reading: a valid purchase is any subset of toys whose total price fits the budget, and we want the subset with the most elements. So enumerate every subset, sum its prices, and remember the largest subset whose sum is ≤ k.
Why this is the honest starting point. Before any insight, 'maximise the count of a subset under a constraint' looks like a search over subsets. Stating the brute force out loud shows the interviewer you understand the shape of the problem — it's combinatorial optimisation — before you simplify it.
Why it's hopeless at scale. There are 2ⁿ subsets. At n = 10⁵, that number has roughly thirty-thousand digits; you couldn't enumerate them before the heat death of the universe. Even at n = 30 it's a billion subsets. The brute force is correct but its only job here is to be rejected.
The hint it gives us. Notice that for a fixed subset size, the cheapest subset of that size is the one most likely to fit. That observation — 'to fit m items, buy the m cheapest' — is the seed of the greedy solution. We don't need to search subsets; we need to sort.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
prices = [3, 7, 2], k = 5{}
sum 0 ≤ 5
best size = 02C · Code with teaching comments
Reference implementation previewpublic int maximumToys(int[] prices, int k) { int n = prices.length; int best = 0; for (int mask = 0; mask < (1 << n); mask++) { long total = 0;Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Brute force over subsets is what you'd do if items had different values. The instant you realise every toy contributes exactly 1 to the answer, the search collapses: among all subsets of size m, the cheapest one dominates, so just take cheapest-first.
ComplexityO(2ⁿ · n) time, O(n) space — There are 2ⁿ subsets and summing each costs up to O(n), giving O(2ⁿ · n). Recursion depth is O(n) for the call stack.
E · Edge cases and pitfalls3Forgetting this is exponential — it only works for tiny n and is a teaching tool, not a submission.Explore edge casesHide edge cases
Pitfalls
- Forgetting this is exponential — it only works for tiny n and is a teaching tool, not a submission.
- Summing into a 32-bit int — overflows once subsets get large.
- Maximising total instead of count — answers the wrong question.
Approach 2 of 2 · Optimal
Greedy — Sort Ascending, Buy Cheapest First (Optimal)
1Hint 1Explore hintHide hint
Every toy adds exactly 1 to the answer. If you wanted to fit as many as possible, which ones would you grab first?
2Hint 2Explore hintHide hint
Sort the prices ascending. Walk from the cheapest, keeping a running total, and buy each toy while the total stays within k.
3Hint 3Explore hintHide hint
The moment the next (more expensive) toy would push you over budget, stop — since the array is sorted, no toy after it can fit either. Return the count bought.
A · Core idea
Sort the prices in ascending order. Keep a running total and a count. Sweep from the cheapest toy: if buying the current toy keeps total ≤ k, buy it (add its price, bump the count); otherwise stop. The count is the answer.
Why cheapest-first is optimal — the exchange argument. Suppose the optimal purchase buys some set S of m toys. Take S and the m cheapest toys overall, call them C. Every toy in C is, by definition, no more expensive than the m-th cheapest, so the total cost of C is ≤ the cost of any other m-toy set, including S. That means C is also affordable (its cost ≤ S's cost ≤ k) and also has m toys. So the cheapest-m prefix achieves the optimum for every achievable m — and the largest m for which the cheapest-m prefix fits is exactly what our sweep finds. There's never a reason to skip a cheaper toy in favour of a pricier one.
Why `break` and not `continue`. Because the array is sorted ascending, the first toy that overshoots the budget is cheaper than every toy after it. If it doesn't fit, none of the later ones do either. So we break immediately — turning what could be a wasted full scan into an early exit. (If the array weren't sorted, this reasoning collapses and you'd be forced back toward search.)
Why the running total needs 64 bits. With up to 10⁵ toys each near 10⁹, the partial sums climb past 2³¹ before we ever exceed a large k. In Java that silently wraps a 32-bit int negative and corrupts the comparison. Use long. Python integers are unbounded, so this is a Java-specific landmine.
Why we add before counting. We test total + price > k first. Only if it passes do we commit the spend and increment the count. Counting first and then checking would let us count a toy we can't actually afford.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
prices = [1, 12, 5, 111, 200, 1000, 10], k = 50Array state
buy 1
total = 1 ≤ 50
4C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The optimal set is always a prefix of the sorted array. That single fact — 'the answer is a prefix' — is what lets us replace a 2ⁿ subset search with one sort and one linear sweep. Whenever a greedy 'take items in sorted order' feels right, look for an exchange argument that proves the prefix is optimal; if you can't construct one, suspect the problem is really DP.
ComplexityO(n log n) time, O(1) space — Sorting is O(n log n) and dominates. The single buying sweep is O(n), and we use only a few scalar variables → O(1) extra space (ignoring the sort's stack).
E · Edge cases and pitfalls6prices = [5, 5, 5], k = 3 — Cheapest toy (5) already exceeds k on the first iteration → break with count 0.Explore edge casesHide edge cases
Edge cases handled
prices = [5, 5, 5], k = 3Cheapest toy (5) already exceeds k on the first iteration → break with count 0.prices = [1, 1, 1], k = 100All toys fit; the loop never breaks and returns n = 3.prices = [1000000000, 1000000000], k = 2000000000Running total reaches 2·10⁹ > int max; long keeps the comparison correct and both toys are bought.
Pitfalls
- Sorting descending — you'd buy the priciest first and undercount badly.
- Using a 32-bit int for the running total — overflow flips it negative and breaks the budget test.
- Using continue instead of break — wastes time and, if you also drop the sort, gives wrong answers.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int maximumToys(int[] prices, int k) { Arrays.sort(prices); long total = 0; int count = 0; for (int price : prices) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Counting the toy before checking the budget
If you increment count and add the price first, then check, you've already counted a toy you can't afford on the overshoot iteration.
Explore the code comparisonHide the code comparison
Counting the toy before checking the budget
If you increment count and add the price first, then check, you've already counted a toy you can't afford on the overshoot iteration.
Don't write this
for (int price : prices) {
total += price;
count++;
if (total > k) break;
}Write this instead
for (int price : prices) {
if (total + price > k) break;
total += price;
count++;
}232-bit overflow on the running total
Up to 10⁵ prices near 10⁹ sum past 2³¹; an int wraps negative and the budget comparison silently passes forever.
Explore the code comparisonHide the code comparison
32-bit overflow on the running total
Up to 10⁵ prices near 10⁹ sum past 2³¹; an int wraps negative and the budget comparison silently passes forever.
Don't write this
int total = 0;
for (int price : prices) {
if (total + price > k) break;
total += price;
}Write this instead
long total = 0;
for (int price : prices) {
if (total + price > k) break;
total += price;
}3Skipping over an unaffordable toy instead of stopping
On a sorted array the first toy that overshoots is cheaper than all that follow, so continue can never find a later toy that fits — it just wastes time and signals you missed the invariant.
Explore the code comparisonHide the code comparison
Skipping over an unaffordable toy instead of stopping
On a sorted array the first toy that overshoots is cheaper than all that follow, so continue can never find a later toy that fits — it just wastes time and signals you missed the invariant.
Don't write this
for price in prices:
if total + price > k:
continue
total += price
count += 1Write this instead
for price in prices:
if total + price > k:
break
total += price
count += 1Revise
Carry the pattern into the interview
Pattern to remember
Greedy by cheapest-first (sort then sweep)
Code pattern to memorize
sort(prices)
total = 0; count = 0
for p in prices:
if total + p > budget: break
total += p; count += 1
return countRules to remember
- 1You're maximising how many toys, not the total value — so spend on the cheapest items first.
- 2Sort ascending, then take a prefix. The answer is always a prefix of the sorted array.
- 3Use
break, notcontinue, the first time a toy overshoots — every later toy is at least as expensive, so none can fit. (True only because the array is sorted.) - 4Add the price before incrementing the count, and check
total + p > budgetso you never count a toy you can't afford. - 5
totalcan exceedintrange if prices and n are large — uselongin Java to be safe.
Use this pattern when
- Maximise the number of items chosen under a single capacity/budget constraint
- Each item has a cost but identical 'value' (you only care about the count)
- No dependency between items — picking one doesn't change another's cost
- The objective is a count, and items can be freely reordered
Choose another pattern when
- Items have different values, not just costs → that's 0/1 Knapsack (DP), not greedy
- You must hit an exact budget, not stay under it → subset-sum / DP
- Picking an item changes other items' availability or cost → greedy breaks
- Multiple constraints (weight AND volume) → multi-dimensional DP
Interview takeaway
When the objective is 'maximise the count under one budget' and all items are interchangeable in value, the exchange argument proves cheapest-first is optimal. This is the same skeleton you'll reuse in activity-selection and any 'fit the most things' greedy.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical 'maximise the count under one budget' greedy. Recognise it whenever items are interchangeable in value and only cost matters — sort ascending and take the longest affordable prefix. Same shape as Assign Cookies and the prefix half of activity-selection.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Maximum Units on a TruckComing soonNow boxes carry different unit counts — sort by units descending and greedily fill the truck.
- 0/1 KnapsackComing soonAdd per-item values and greedy breaks — you need DP over capacity.
- Assign CookiesComing soonSame sort-and-sweep skeleton: match smallest cookie to the least greedy child.
- Two City SchedulingComing soonGreedy by the cost difference, then take a sorted prefix.