Loading…

easyGreedySometimes asked

Luck Balance

Q: How do you solve Luck Balance using the Brute Force — Try Every Choice of Which Important Contests to Lose approach?

When to use it: Mention it to show you see the search space, then collapse it with the greedy observation about unimportant contests. Strip out the easy half first: every unimportant contest should be lost, contributing `+L` with no constraint. That part needs no search. **Where the real search lives.** The only genuine decision is *which* important contests to lose, subject to losing at most `k` of them. A brute force enumerates every subset of the important contests with size ≤ k, treats those as losses (+L) and the rest as wins (−L), and keeps the maximum balance. **Why it's correct but wasteful.** Trying all subsets is guaranteed to find the best assignment, but there are up to `2^m` subsets where `m` is the count of important contests. Even though n ≤ 100 here, this is exponential and pointless once you spot the structure. **The structure it reveals.** Among all size-k subsets, the one that maximises the gain is obviously the k *largest* luck values — losing a big contest adds more than losing a small one, and being forced to win a small one subtracts less than winning a big one. That single observation replaces the entire subset search with a sort. Time complexity: O(2^m · m). Space complexity: O(m).

Q: How do you solve Luck Balance using the Greedy — Sort Important Descending, Lose the Top k (Optimal) approach?

When to use it: The answer they want. Phrase it as 'spend my k allowed losses on the biggest important contests'. Split the contests into two buckets. **Unimportant** contests are unconstrained, so lose every one of them — add all their luck to a running `base`. **Important** contests are capped at `k` losses, so collect their luck values, sort them descending, lose (add) the first `k`, and win (subtract) the remaining ones. **Why every unimportant contest is lost.** Losing adds `+L` with `L ≥ 1`, and there's no limit on unimportant losses. There is literally never a reason to win one — winning would subtract luck we could instead gain. So they contribute their entire sum to the answer with no decision to make. **Why the k losses go to the largest important contests — the exchange argument.** Suppose an optimal solution loses a smaller important contest with luck `a` while winning a larger one with luck `b > a`. The two together contribute `+a − b`. Swap them — lose `b`, win `a` — and they now contribute `+b − a`, which is larger by `2(b − a) > 0`. So any solution that doesn't spend its losses on the largest values can be strictly improved. Therefore the optimal assignment loses exactly the k largest important contests. Sorting descending and taking the prefix of length k realises this directly. **Why the remaining important contests are subtracted.** Once the k loss-slots are used up, every other important contest *must* be won, and winning subtracts its luck. There's no third option — the cap forces it. Getting this sign wrong is the most common silent bug here. **The k ≥ m corner.** If there are fewer important contests than k, every important contest is lost and none is won — the 'win' branch simply never executes. The index check `i < k` handles this without a special case. Time complexity: O(n log n). Space complexity: O(n).

Greedy Algorithms · 7 of 23 · 8 min

Lena is preparing for an important coding contest by competing in n preliminary contests. Each contest i has a luck amount L[i] and an importance flag T[i] (1 = important, 0 = unimportant).

If Lena wins a contest, her luck balance decreases by L[i]. If she loses, her luck balance increases by L[i].

She wants to maximise her luck balance but can lose at most `k` of the important contests. She may lose any number of unimportant contests. Return the maximum luck balance she can achieve.

In plain English

Each contest is a choice: lose (+L) or win (−L). Unimportant contests are unconstrained, so we always lose them. Important contests are capped — we may lose at most k of them — so we lose the most valuable k and are forced to win (subtract) the remaining important ones.

Examples

Example 1

Input: k = 3, contests = [[5,1],[2,1],[1,1],[8,1],[10,0],[5,0]]
Output: 29
Note: Unimportant: lose both (10 + 5 = 15). Important sorted desc: [8,5,2,1]; lose top 3 (8+5+2=15), win rest (−1). Total 15 + 15 − 1 = 29.

Example 2

Input: k = 3, contests = [[5,1],[1,1],[4,0]]
Output: 10
Note: Lose unimportant 4. Only 2 important contests and k=3, so lose both: 4 + 5 + 1 = 10. No win needed.

Example 3

Input: k = 0, contests = [[3,1],[7,1],[2,0]]
Output: −8
Note: Lose unimportant 2. With k=0 we must win every important contest: 2 − 3 − 7 = −8.

Constraints

1 ≤ n ≤ 100
0 ≤ k ≤ n
1 ≤ L[i] ≤ 10⁴
T[i] ∈ {0, 1}

Clarifying questions4First question: Does the cap k apply to all contests or only important ones?Explore questions

Q1.Does the cap k apply to all contests or only important ones?
Only important contests. Unimportant ones can be lost freely with no limit.
Q2.Do I have to lose exactly k important contests, or at most k?
At most k. If there are fewer than k important contests, just lose all of them and win none.
Q3.What's the sign convention — does winning help or hurt my luck?
Winning DECREASES luck (−L); losing INCREASES it (+L). We want to maximise, so losses are good.
Q4.Can luck values be negative?
No, L[i] ≥ 1, so every loss strictly increases the balance — that's why we lose every unimportant contest.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Lose every unimportant contest for free (each loss ADDS its luck), and among the important contests lose the k with the largest luck and win the rest (winning SUBTRACTS luck). Sort the important contests by luck descending, add the top k, subtract the others. O(n log n) from the sort.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you separate the unconstrained part (lose all unimportant contests) from the constrained part (at most k important losses), and then greedily assign the k losses to the highest-luck important contests.

Where candidates slip

Forgetting that unimportant contests should all be lost regardless of k, or flipping the sign so winning adds luck — both silently produce a wrong total.

How to stand out

State the exchange argument: if a loss were spent on a smaller important contest while a larger one was won, swapping them increases the total — so the k losses must go to the largest luck values.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Choice of Which Important Contests to Lose	`O(2^m · m)`	`O(m)`	Mention it to show you see the search space, then collapse it with the greedy observation about unimportant contests.	Read
2	Greedy — Sort Important Descending, Lose the Top k (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want. Phrase it as 'spend my k allowed losses on the biggest important contests'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewEach contest: L luck, T importanceImportant (T = 1)?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Choice of Which Important Contests to Lose

TimeO(2^m · m)SpaceO(m)

Mention it to show you see the search space, then collapse it with the greedy observation about unimportant contests.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Unimportant contests are easy — what's the only sensible thing to do with a loss that costs nothing and only adds luck?

2Hint 2Explore hint

For the important contests, the real decision is which subset (of size ≤ k) to lose. How many such subsets are there?

3Hint 3Explore hint

Enumerate every valid subset of important contests to lose, compute the resulting balance, and keep the maximum. Correct, but exponential in the number of important contests.

A · Core idea

Strip out the easy half first: every unimportant contest should be lost, contributing +L with no constraint. That part needs no search.

Where the real search lives. The only genuine decision is which important contests to lose, subject to losing at most k of them. A brute force enumerates every subset of the important contests with size ≤ k, treats those as losses (+L) and the rest as wins (−L), and keeps the maximum balance.

Why it's correct but wasteful. Trying all subsets is guaranteed to find the best assignment, but there are up to 2^m subsets where m is the count of important contests. Even though n ≤ 100 here, this is exponential and pointless once you spot the structure.

The structure it reveals. Among all size-k subsets, the one that maximises the gain is obviously the k largest luck values — losing a big contest adds more than losing a small one, and being forced to win a small one subtracts less than winning a big one. That single observation replaces the entire subset search with a sort.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

k = 1, important luck = [5, 2]

lose none

win both: −5 −2 = −7

Statebest = −7

Final resultlose the larger (5) → +3 from the important contests

C · Code with teaching comments

Reference implementation previewpublic int luckBalance(int k, int[][] contests) { List<Integer> important = new ArrayList<>(); int base = 0; for (int[] c : contests) { if (c[1] == 0) base += c[0];Explore the full code

solution.javaJava

Brute Force — Try Every Choice of Which Important Contests to Lose — reference

3 teaching notes

1
public int luckBalance(int k, int[][] contests) {
2
    List<Integer> important = new ArrayList<>();
3
    int base = 0;
4
    for (int[] c : contests) {
5
        // Unimportant contest — always lost, so add its luck unconditionally.
6
        if (c[1] == 0) base += c[0];
7
        else important.add(c[0]);
8
    }
9
    int m = important.size();
10
    int best = Integer.MIN_VALUE;
11
    for (int mask = 0; mask < (1 << m); mask++) {
12
        // Skip subsets that lose more than k important contests — they violate the cap.
13
        if (Integer.bitCount(mask) > k) continue;
14
        int luck = base;
15
        for (int i = 0; i < m; i++) {
16
            // Bit set means lose (+L); bit clear means win (−L).
17
            luck += ((mask & (1 << i)) != 0) ? important.get(i) : -important.get(i);
18
        }
19
        best = Math.max(best, luck);
20
    }
21
    return best;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(2^m · m) timeO(m) spaceOpen the invariant and proofExplore the proof

The brute force only struggles on the important contests, and even there the answer is monotone: bigger luck always prefers to be lost. Monotone preference under a count cap is the textbook signal to sort and take the top k.

ComplexityO(2^m · m) time, O(m) space — There are up to 2^m subsets of the m important contests (filtered to size ≤ k), and scoring each costs O(m). Unimportant contests are summed once in O(n).

E · Edge cases and pitfalls3Putting unimportant contests into the subset search — they have no cap, so they don't belong there.Explore edge cases

Pitfalls

Putting unimportant contests into the subset search — they have no cap, so they don't belong there.
Counting subsets larger than k — violates the constraint.
Exponential blow-up — only viable for tiny m; use it to motivate the greedy.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort Important Descending, Lose the Top k (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want. Phrase it as 'spend my k allowed losses on the biggest important contests'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Unimportant contests have no cap and only help — what should you always do with them?

2Hint 2Explore hint

Now you have a budget of k losses to spend on important contests. Which important contests give the biggest swing when lost rather than won?

3Hint 3Explore hint

Sort the important luck values descending. Add the first k (losses), subtract the rest (forced wins), and add the full sum of unimportant luck. Done in one pass after the sort.

A · Core idea

Split the contests into two buckets. Unimportant contests are unconstrained, so lose every one of them — add all their luck to a running base. Important contests are capped at k losses, so collect their luck values, sort them descending, lose (add) the first k, and win (subtract) the remaining ones.

Why every unimportant contest is lost. Losing adds +L with L ≥ 1, and there's no limit on unimportant losses. There is literally never a reason to win one — winning would subtract luck we could instead gain. So they contribute their entire sum to the answer with no decision to make.

Why the k losses go to the largest important contests — the exchange argument. Suppose an optimal solution loses a smaller important contest with luck a while winning a larger one with luck b > a. The two together contribute +a − b. Swap them — lose b, win a — and they now contribute +b − a, which is larger by 2(b − a) > 0. So any solution that doesn't spend its losses on the largest values can be strictly improved. Therefore the optimal assignment loses exactly the k largest important contests. Sorting descending and taking the prefix of length k realises this directly.

Why the remaining important contests are subtracted. Once the k loss-slots are used up, every other important contest must be won, and winning subtracts its luck. There's no third option — the cap forces it. Getting this sign wrong is the most common silent bug here.

The k ≥ m corner. If there are fewer important contests than k, every important contest is lost and none is won — the 'win' branch simply never executes. The index check i < k handles this without a special case.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

k = 3, contests = [[5,1],[2,1],[1,1],[8,1],[10,0],[5,0]]

Array state

i=0 (8)

i < 3 → lose, +8

i ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result29

C · Code with teaching comments

solution.javaJava

Greedy — Sort Important Descending, Lose the Top k (Optimal) — optimal

3 teaching notes

1
public int luckBalance(int k, int[][] contests) {
2
    List<Integer> important = new ArrayList<>();
3
    int luck = 0;
4
    for (int[] c : contests) {
5
        // Unimportant contest — always lost, so unconditionally add its luck.
6
        if (c[1] == 0) {
7
            luck += c[0];
8
        } else {
9
            important.add(c[0]);
10
        }
11
    }
12
    // Descending sort puts the biggest-swing contests first, where the k losses pay off
13
    // most.
14
    important.sort(Comparator.reverseOrder());
15
    for (int i = 0; i < important.size(); i++) {
16
        // First k important contests are lost (+L); the rest are forced wins (−L).
17
        luck += (i < k) ? important.get(i) : -important.get(i);
18
    }
19
    return luck;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

The problem factors cleanly into a free part (sum all unimportant luck) and a capped part (a top-k selection among important contests). Spotting that the cap only binds on one bucket is what reduces a 2^m search to a sort. 'Free choices + one capped greedy selection' is a recurring decomposition — isolate the constraint, then sort within it.

ComplexityO(n log n) time, O(n) space — Bucketing the contests is O(n); sorting the important list is O(m log m) ≤ O(n log n) and dominates. We store the important values → O(n) space.

E · Edge cases and pitfalls6k = 0, important = [3, 7] — No losses allowed; every important contest is won → −3 − 7 = −10 added to base.Explore edge cases

Edge cases handled

k = 0, important = [3, 7]No losses allowed; every important contest is won → −3 − 7 = −10 added to base.
k ≥ number of important contestsEvery i < k, so all important contests are lost — the win branch never runs.
no important contestsThe important list is empty; luck is just the sum of all unimportant losses.

Pitfalls

Sorting ascending — you'd lose the smallest important contests and win the largest, minimising instead of maximising.
Flipping the sign so wins add and losses subtract — inverts the whole answer.
Applying the cap k to unimportant contests — they have no cap and should all be lost.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int luckBalance(int k, int[][] contests) { List<Integer> important = new ArrayList<>(); int luck = 0; for (int[] c : contests) { if (c[1] == 0) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Sorting important contests ascending

You must spend the k losses on the LARGEST important contests; ascending order loses the smallest ones and wins the biggest, which minimises luck.

Explore the code comparison

Don't write this

important.sort(Comparator.naturalOrder());
for (int i = 0; i < important.size(); i++) {
    luck += (i < k) ? important.get(i) : -important.get(i);
}

Write this instead

important.sort(Comparator.reverseOrder());
for (int i = 0; i < important.size(); i++) {
    luck += (i < k) ? important.get(i) : -important.get(i);
}

Inverting the win/lose sign

Losing ADDS luck and winning SUBTRACTS it. Swapping the signs makes the algorithm minimise the balance.

Explore the code comparison

Don't write this

luck += -amount if i < k else amount

Write this instead

luck += amount if i < k else -amount

Applying the cap to unimportant contests

Only important contests are capped at k losses. Unimportant contests have no limit and must all be lost for full luck.

Explore the code comparison

Don't write this

all_luck = sorted([amount for amount, _ in contests], reverse=True)
luck = sum(a if i < k else -a for i, a in enumerate(all_luck))

Write this instead

for amount, is_important in contests:
    if is_important == 0:
        luck += amount
    else:
        important.append(amount)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy with a constrained budget of 'losses' (sort important desc, lose the biggest k)

Code pattern to memorize

luck = 0
for (L, important) in contests:
    if not important: luck += L          # lose all unimportant — free
    else: importantLuck.append(L)
sort importantLuck descending
for i, L in enumerate(importantLuck):
    luck += L if i < k else -L           # lose top k, win the rest

Rules to remember

1Always lose unimportant contests — there's no cap on them and each loss only adds luck.
2For important contests you may lose at most k; spend those k losses on the largest luck values for maximum gain.
3Sort important contests descending and split at index k: indices < k are losses (+L), the rest are wins (-L).
4Winning a contest subtracts its luck — losing adds it. Get the sign right or the answer flips.
5If there are fewer than k important contests, you simply lose them all (you never have to win any).

Use this pattern when

You have a hard cap on how many 'costly' choices you can make and want to maximise a sum
Each item contributes +value if chosen one way, −value the other, with a count limit on the favourable choice
Items split into 'free' (no limit) and 'capped' groups
The favourable action should clearly go to the largest-magnitude items

Choose another pattern when

The cap interacts across items (losing one changes another's value) → greedy breaks, think DP
You must lose EXACTLY k, not at most k → still greedy here, but watch the boundary
Multiple resource caps at once → multi-dimensional optimisation
Values can be negative or the +/− rule is conditional → re-derive the exchange argument

Interview takeaway

When a limited 'budget' of favourable choices buys you +value vs −value per item, spend the budget on the largest items. Sort descending, take the top k. This 'biggest-first under a count cap' move shows up across greedy problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternGreedy top-k under a count cap. Decompose into a free bucket (always take the favourable action) and a capped bucket (sort by magnitude, take the best k). Same skeleton appears wherever a limited budget of favourable choices should go to the largest-magnitude items.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Mark and Toys
Another sort-and-prefix greedy — buy the cheapest items under a budget.
Maximum Subarray (Kadane)
Coming soon
Different lens, same goal of maximising a running total of signed contributions.
Greedy Florist
Sort and assign costliest items to minimise a multiplier — another sort-by-magnitude greedy.
Maximize Toys / Assign Cookies
Coming soon
Capped greedy matching with a sorted prefix.

Same pattern

←

Jumping on the Clouds

Continue · Next problem

Mark and Toys

easyGreedySometimes asked

Luck Balance

Greedy Algorithms · 7 of 23 · 8 min

Lena is preparing for an important coding contest by competing in n preliminary contests. Each contest i has a luck amount L[i] and an importance flag T[i] (1 = important, 0 = unimportant).

If Lena wins a contest, her luck balance decreases by L[i]. If she loses, her luck balance increases by L[i].

She wants to maximise her luck balance but can lose at most `k` of the important contests. She may lose any number of unimportant contests. Return the maximum luck balance she can achieve.

In plain English

Examples

Example 1

Input: k = 3, contests = [[5,1],[2,1],[1,1],[8,1],[10,0],[5,0]]
Output: 29
Note: Unimportant: lose both (10 + 5 = 15). Important sorted desc: [8,5,2,1]; lose top 3 (8+5+2=15), win rest (−1). Total 15 + 15 − 1 = 29.

Example 2

Input: k = 3, contests = [[5,1],[1,1],[4,0]]
Output: 10
Note: Lose unimportant 4. Only 2 important contests and k=3, so lose both: 4 + 5 + 1 = 10. No win needed.

Example 3

Input: k = 0, contests = [[3,1],[7,1],[2,0]]
Output: −8
Note: Lose unimportant 2. With k=0 we must win every important contest: 2 − 3 − 7 = −8.

Constraints

1 ≤ n ≤ 100
0 ≤ k ≤ n
1 ≤ L[i] ≤ 10⁴
T[i] ∈ {0, 1}

Clarifying questions4First question: Does the cap k apply to all contests or only important ones?Explore questions

Q1.Does the cap k apply to all contests or only important ones?
Only important contests. Unimportant ones can be lost freely with no limit.
Q2.Do I have to lose exactly k important contests, or at most k?
At most k. If there are fewer than k important contests, just lose all of them and win none.
Q3.What's the sign convention — does winning help or hurt my luck?
Winning DECREASES luck (−L); losing INCREASES it (+L). We want to maximise, so losses are good.
Q4.Can luck values be negative?
No, L[i] ≥ 1, so every loss strictly increases the balance — that's why we lose every unimportant contest.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Forgetting that unimportant contests should all be lost regardless of k, or flipping the sign so winning adds luck — both silently produce a wrong total.

How to stand out

State the exchange argument: if a loss were spent on a smaller important contest while a larger one was won, swapping them increases the total — so the k losses must go to the largest luck values.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Choice of Which Important Contests to Lose	`O(2^m · m)`	`O(m)`	Mention it to show you see the search space, then collapse it with the greedy observation about unimportant contests.	Read
2	Greedy — Sort Important Descending, Lose the Top k (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want. Phrase it as 'spend my k allowed losses on the biggest important contests'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Choice of Which Important Contests to Lose

TimeO(2^m · m)SpaceO(m)

Mention it to show you see the search space, then collapse it with the greedy observation about unimportant contests.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Unimportant contests are easy — what's the only sensible thing to do with a loss that costs nothing and only adds luck?

2Hint 2Explore hint

For the important contests, the real decision is which subset (of size ≤ k) to lose. How many such subsets are there?

3Hint 3Explore hint

Enumerate every valid subset of important contests to lose, compute the resulting balance, and keep the maximum. Correct, but exponential in the number of important contests.

A · Core idea

Strip out the easy half first: every unimportant contest should be lost, contributing +L with no constraint. That part needs no search.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

k = 1, important luck = [5, 2]

lose none

win both: −5 −2 = −7

Statebest = −7

Final resultlose the larger (5) → +3 from the important contests

C · Code with teaching comments

solution.javaJava

Brute Force — Try Every Choice of Which Important Contests to Lose — reference

3 teaching notes

1
public int luckBalance(int k, int[][] contests) {
2
    List<Integer> important = new ArrayList<>();
3
    int base = 0;
4
    for (int[] c : contests) {
5
        // Unimportant contest — always lost, so add its luck unconditionally.
6
        if (c[1] == 0) base += c[0];
7
        else important.add(c[0]);
8
    }
9
    int m = important.size();
10
    int best = Integer.MIN_VALUE;
11
    for (int mask = 0; mask < (1 << m); mask++) {
12
        // Skip subsets that lose more than k important contests — they violate the cap.
13
        if (Integer.bitCount(mask) > k) continue;
14
        int luck = base;
15
        for (int i = 0; i < m; i++) {
16
            // Bit set means lose (+L); bit clear means win (−L).
17
            luck += ((mask & (1 << i)) != 0) ? important.get(i) : -important.get(i);
18
        }
19
        best = Math.max(best, luck);
20
    }
21
    return best;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(2^m · m) timeO(m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Putting unimportant contests into the subset search — they have no cap, so they don't belong there.Explore edge cases

Pitfalls

Putting unimportant contests into the subset search — they have no cap, so they don't belong there.
Counting subsets larger than k — violates the constraint.
Exponential blow-up — only viable for tiny m; use it to motivate the greedy.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort Important Descending, Lose the Top k (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want. Phrase it as 'spend my k allowed losses on the biggest important contests'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Unimportant contests have no cap and only help — what should you always do with them?

2Hint 2Explore hint

Now you have a budget of k losses to spend on important contests. Which important contests give the biggest swing when lost rather than won?

3Hint 3Explore hint

Sort the important luck values descending. Add the first k (losses), subtract the rest (forced wins), and add the full sum of unimportant luck. Done in one pass after the sort.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

k = 3, contests = [[5,1],[2,1],[1,1],[8,1],[10,0],[5,0]]

Array state

i=0 (8)

i < 3 → lose, +8

i ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result29

C · Code with teaching comments

solution.javaJava

Greedy — Sort Important Descending, Lose the Top k (Optimal) — optimal

3 teaching notes

1
public int luckBalance(int k, int[][] contests) {
2
    List<Integer> important = new ArrayList<>();
3
    int luck = 0;
4
    for (int[] c : contests) {
5
        // Unimportant contest — always lost, so unconditionally add its luck.
6
        if (c[1] == 0) {
7
            luck += c[0];
8
        } else {
9
            important.add(c[0]);
10
        }
11
    }
12
    // Descending sort puts the biggest-swing contests first, where the k losses pay off
13
    // most.
14
    important.sort(Comparator.reverseOrder());
15
    for (int i = 0; i < important.size(); i++) {
16
        // First k important contests are lost (+L); the rest are forced wins (−L).
17
        luck += (i < k) ? important.get(i) : -important.get(i);
18
    }
19
    return luck;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(n) space — Bucketing the contests is O(n); sorting the important list is O(m log m) ≤ O(n log n) and dominates. We store the important values → O(n) space.

E · Edge cases and pitfalls6k = 0, important = [3, 7] — No losses allowed; every important contest is won → −3 − 7 = −10 added to base.Explore edge cases

Edge cases handled

k = 0, important = [3, 7]No losses allowed; every important contest is won → −3 − 7 = −10 added to base.
k ≥ number of important contestsEvery i < k, so all important contests are lost — the win branch never runs.
no important contestsThe important list is empty; luck is just the sum of all unimportant losses.

Pitfalls

Sorting ascending — you'd lose the smallest important contests and win the largest, minimising instead of maximising.
Flipping the sign so wins add and losses subtract — inverts the whole answer.
Applying the cap k to unimportant contests — they have no cap and should all be lost.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int luckBalance(int k, int[][] contests) { List<Integer> important = new ArrayList<>(); int luck = 0; for (int[] c : contests) { if (c[1] == 0) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Sorting important contests ascending

You must spend the k losses on the LARGEST important contests; ascending order loses the smallest ones and wins the biggest, which minimises luck.

Explore the code comparison

Don't write this

important.sort(Comparator.naturalOrder());
for (int i = 0; i < important.size(); i++) {
    luck += (i < k) ? important.get(i) : -important.get(i);
}

Write this instead

important.sort(Comparator.reverseOrder());
for (int i = 0; i < important.size(); i++) {
    luck += (i < k) ? important.get(i) : -important.get(i);
}

Inverting the win/lose sign

Losing ADDS luck and winning SUBTRACTS it. Swapping the signs makes the algorithm minimise the balance.

Explore the code comparison

Don't write this

luck += -amount if i < k else amount

Write this instead

luck += amount if i < k else -amount

Applying the cap to unimportant contests

Only important contests are capped at k losses. Unimportant contests have no limit and must all be lost for full luck.

Explore the code comparison

Don't write this

all_luck = sorted([amount for amount, _ in contests], reverse=True)
luck = sum(a if i < k else -a for i, a in enumerate(all_luck))

Write this instead

for amount, is_important in contests:
    if is_important == 0:
        luck += amount
    else:
        important.append(amount)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy with a constrained budget of 'losses' (sort important desc, lose the biggest k)

Code pattern to memorize

luck = 0
for (L, important) in contests:
    if not important: luck += L          # lose all unimportant — free
    else: importantLuck.append(L)
sort importantLuck descending
for i, L in enumerate(importantLuck):
    luck += L if i < k else -L           # lose top k, win the rest

Rules to remember

1Always lose unimportant contests — there's no cap on them and each loss only adds luck.
2For important contests you may lose at most k; spend those k losses on the largest luck values for maximum gain.
3Sort important contests descending and split at index k: indices < k are losses (+L), the rest are wins (-L).
4Winning a contest subtracts its luck — losing adds it. Get the sign right or the answer flips.
5If there are fewer than k important contests, you simply lose them all (you never have to win any).

Use this pattern when

You have a hard cap on how many 'costly' choices you can make and want to maximise a sum
Each item contributes +value if chosen one way, −value the other, with a count limit on the favourable choice
Items split into 'free' (no limit) and 'capped' groups
The favourable action should clearly go to the largest-magnitude items

Choose another pattern when

The cap interacts across items (losing one changes another's value) → greedy breaks, think DP
You must lose EXACTLY k, not at most k → still greedy here, but watch the boundary
Multiple resource caps at once → multi-dimensional optimisation
Values can be negative or the +/− rule is conditional → re-derive the exchange argument

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Mark and Toys
Another sort-and-prefix greedy — buy the cheapest items under a budget.
Maximum Subarray (Kadane)
Coming soon
Different lens, same goal of maximising a running total of signed contributions.
Greedy Florist
Sort and assign costliest items to minimise a multiplier — another sort-by-magnitude greedy.
Maximize Toys / Assign Cookies
Coming soon
Capped greedy matching with a sorted prefix.

Same pattern

←

Jumping on the Clouds

Continue · Next problem

Mark and Toys