easy Buy Two Chocolates

Problem statement

You are in a chocolate shop where each chocolate has a price, as listed in an array prices. With a certain amount of money in your pocket, you aim to purchase exactly two chocolates.

You would like to minimize the combined cost of these chocolates so that you are left with as much money as possible, without going into debt.

Calculate the amount of money you'll have left after making the purchase. If it's not possible to buy two chocolates without overspending, return the original amount of money you had.

Examples

Example 1:

Input: prices = [2, 5, 3, 9], money = 10
Expected Output: 5
Justification: The optimal choice is to buy chocolates priced at 2 and 3, costing a total of 5. Therefore, you're left with 10 - 5 = 5.

Example 2:

Input: prices = [10, 20, 15, 5, 25, 30, 35, 40], money = 50
Expected Output: 35
Justification: The cheapest two chocolates has cost 5 and 10. Purchasing these costs 15 in total. Thus, you are left with 50 - 15 = 35.

Example 3:

Input: prices = [7, 1, 5, 3], money = 3
Expected Output: 3
Justification: It's impossible to buy two chocolates without going into debt, so you keep your original amount of 3.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Buy Two Chocolates — problem

1. Why / judgment

Buy exactly two distinct chocolates minimizing cost (equivalently: sum of the two cheapest). If that sum exceeds money, return money unchanged. Pattern is one-pass two-minima or sort-and-take-first-two — not knapsack (fixed cardinality 2).

2. Big-O derivation (K11)

One pass track min1,min2: O(n) time O(1) space.
Sort: O(n log n) time.
Answer: money−(min1+min2) if ≤money else money.

3. Pattern + when-NOT (K12)

Name: TWO MINIMA / GREEDY FIXED-K CHEAPEST

Recognition: exactly two purchases; maximize leftover without debt.

When-NOT: Need k of n with k large → heap/sort. Need any subset under budget maximizing count → different greedy/knapsack. Prices can be negative → problem usually assumes non-negative; state assumption.

4. Edge hand-run (K13)

n=2 always only one pair.
prices all > money/2 carefully: may still afford two small.
money < sum of two cheapest → return money.
duplicates prices OK.

5. Interviewer follow-ups (model answers)

Q1. Why not full knapsack?
A: Cardinality fixed at 2 and objective is min sum of two — closed form via two minima.

Q2. Must indices be distinct?
A: Yes — two chocolates; even if same price, need two elements.

Q3. Sort vs one-pass?
A: One-pass O(n) better; sort only if also need order elsewhere.

6. Short drills

Drill: [2,5,3,9] money=10 → 5.
Drill: [3,2,3] money=3 → 3 (cannot buy).

✅ Solution Buy Two Chocolates

Problem statement

You are in a chocolate shop where each chocolate has a price, as listed in an array prices. With a certain amount of money in your pocket, you aim to purchase exactly two chocolates.

You would like to minimize the combined cost of these chocolates so that you are left with as much money as possible, without going into debt.

Calculate the amount of money you'll have left after making the purchase. If it's not possible to buy two chocolates without overspending, return the original amount of money you had.

Examples

Example 1:

Input: prices = [2, 5, 3, 9], money = 10
Expected Output: 5
Justification: The optimal choice is to buy chocolates priced at 2 and 3, costing a total of 5. Therefore, you're left with 10 - 5 = 5.

Example 2:

Input: prices = [10, 20, 15, 5, 25, 30, 35, 40], money = 50
Expected Output: 35
Justification: The cheapest two chocolates has cost 5 and 10. Purchasing these costs 15 in total. Thus, you are left with 50 - 15 = 35.

Example 3:

Input: prices = [7, 1, 5, 3], money = 3
Expected Output: 3
Justification: It's impossible to buy two chocolates without going into debt, so you keep your original amount of 3.

Solution

To solve this problem, we first sort the array of chocolate prices in ascending order. This arrangement allows us to easily identify the two cheapest chocolates, as they will be positioned at the beginning of the sorted array. By purchasing these two chocolates, we ensure that we spend the minimum possible amount of our budget, thereby maximizing the leftover money. Subtracting the total cost of these two chocolates from the initial amount of money provides us with the desired result. This approach is both straightforward and efficient, as it leverages sorting to quickly solve the problem.

Step-by-step Algorithm

Sort the array of chocolate prices in ascending order.
Select the first two elements of the sorted array as they represent the cheapest chocolates.
Calculate the sum of the prices of these two chocolates.
Subtract this sum from the initial amount of money to find the leftover money.
Return the leftover money. If the sum of the prices of the two cheapest chocolates exceeds the initial amount of money, it indicates that it's not possible to buy two chocolates without going into debt; hence, return the original amount of money in such a case.

Algorithm Walkthrough

Given the input prices = [10, 20, 15, 5, 25, 30, 35, 40], money = 50:

Sort the prices array: First, we sort the array of chocolate prices to easily identify the cheapest options. The sorted array becomes [5, 10, 15, 20, 25, 30, 35, 40].
Identify the two cheapest chocolates: The two cheapest chocolates are the first two elements of the sorted array, which are priced at 5 and 10.
Calculate the total cost of these chocolates: We add the prices of these two chocolates together, resulting in a total cost of 5 + 10 = 15.
Determine if the purchase is possible within the budget: Before making the purchase, we need to ensure that the total cost of the two chocolates does not exceed our budget of 50. In this case, 15 is less than 50, which means the purchase is within our budget.
Calculate the leftover money: Since the total cost of 15 is within our budget, we subtract this amount from our initial money to determine how much will be left after the purchase. Therefore, we perform the calculation 50 - 15 = 35.
Return the result: The algorithm returns 35, indicating the amount of money left after buying the two cheapest chocolates from the sorted list.

Code

java

import java.util.Arrays;

public class Solution {

  // Calculate the leftover money after buying the two cheapest chocolates
  public int maxLeftover(int[] prices, int money) {
    Arrays.sort(prices); // Sort the prices array
    // Ensure there are at least two chocolates to buy
    if (prices.length < 2 || prices[0] + prices[1] > money) {
      return money; // Return the original amount if not enough to buy two
    }
    return money - (prices[0] + prices[1]); // Subtract the cost of two cheapest chocolates from the money
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] prices1 = { 2, 5, 3, 9 };
    int money1 = 10;
    System.out.println(
      "Leftover money for Example 1: " + solution.maxLeftover(prices1, money1)
    );

    // Example 2
    int[] prices2 = { 10, 20, 15, 5, 25, 30, 35, 40 };
    int money2 = 50;
    System.out.println(
      "Leftover money for Example 2: " + solution.maxLeftover(prices2, money2)
    );

    // Example 3
    int[] prices3 = { 7, 1, 5, 3 };
    int money3 = 3;
    System.out.println(
      "Leftover money for Example 3: " + solution.maxLeftover(prices3, money3)
    );
  }
}

Complexity Analysis

Time Complexity: due to the sorting step, where n is the number of chocolates (or elements in the array). This is the dominant factor in the time complexity.
Space Complexity: for the additional space used (ignoring the space for the input array). This accounts for the constants and minimal extra variables used in the algorithm. If considering the sorting algorithm's space usage, it could be for in-place sorting algorithms like QuickSort due to recursive stack space.

🎯 STRICT STANDOUT — Solution Buy Two Chocolates

1. Why / judgment

Single scan maintains (min1 ≤ min2). Correctness: optimal pair is always the two global minima among non-negative prices. After scan, if min1+min2 ≤ money return money−sum else money.

2. Big-O derivation (K11)

O(n) comparisons, O(1) extra.
Trace [2,5,3,9]: min1=2 min2=3 sum=5 ≤10 → 5.
Trace [10,20,...,5] money=50: min1=5 min2=10 → 35.

3. Pattern + when-NOT (K12)

Name: ONE-PASS TWO MINIMA

Recognition: fixed buy count = 2; max leftover.

When-NOT: k>2 cheapest → heap of size k or sort. Need product max of two → track two maxima (and sign cases).

4. Edge hand-run (K13)

n=2 [1,2] money=2 → 0 if sum=3>2 wait sum=3>2 → money; if money=3 → 0.
all equal [4,4,4] money=8 → 0.
money=0 → 0.

5. Interviewer follow-ups (model answers)

Q1. Initialize min1/min2?
A: Use +∞ sentinels or first two elements carefully ordered.

Q2. Stable if three equal minima?
A: Any two of them work; sum identical.

Q3. Overflow on sum?
A: Constraints usually small; still prefer checked add in strict languages.

6. Short drills

Drill: implement without sorting.
Drill: edge money exactly min1+min2 → 0 leftover.

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Buy Two Chocolates? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Buy Two Chocolates** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Buy Two Chocolates** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Buy Two Chocolates**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Buy Two Chocolates**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Move Zeroes Transpose Matrix →