#2706

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Buy Two Chocolates

Determine the leftover money after buying exactly two chocolates using a greedy selection and sum validation approach.

Problem Statement

You are given an array prices where each element represents the price of a chocolate in a store, along with an integer money representing your available funds. You must buy exactly two chocolates while ensuring you do not spend more than your available money.

Return the remaining amount of money after buying the two chocolates. If no combination of two chocolates fits within your budget, return the original money amount. Your goal is to minimize the sum of the two chosen chocolate prices while keeping the leftover non-negative.

Examples

Example 1

Input: prices = [1,2,2], money = 3

Output: 0

Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 - 3 = 0 units of money afterwards. Thus, we return 0.

Example 2

Input: prices = [3,2,3], money = 3

Output: 3

You cannot buy 2 chocolates without going in debt, so we return 3.

Constraints

2 <= prices.length <= 50
1 <= prices[i] <= 100
1 <= money <= 100

Solution Approach

Sort Prices for Greedy Selection

Start by sorting the prices array in ascending order. This ensures the two cheapest chocolates are at the beginning, allowing a greedy choice that minimizes total cost.

Check Feasibility of Purchase

Add the two smallest prices and compare with the money. If the sum is less than or equal to the available money, proceed with the purchase; otherwise, return money since no valid pair exists.

Calculate and Return Leftover

Subtract the sum of the selected two chocolates from money to find the leftover. This step validates the invariant that the leftover must remain non-negative and completes the greedy approach.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Sorting the array is optional but ensures a direct greedy choice; iterating to find two smallest prices takes O(n) time and O(1) space for a fixed-size array.

What Interviewers Usually Probe

Are you using the two cheapest chocolates to minimize cost?
Did you consider what happens if money is insufficient for any two chocolates?
Can you solve this without sorting the entire array?

Common Pitfalls or Variants

Common pitfalls

Failing to check if money is enough before subtracting prices.
Choosing any two chocolates without ensuring the sum is minimal.
Assuming leftover can be negative, violating the non-negative requirement.

Follow-up variants

Buy three chocolates instead of two, still minimizing total cost.
Maximize leftover money rather than minimizing chocolate cost.
Allow repeated purchase of the same chocolate if prices permit.

FAQ

How does the greedy pattern apply to Buy Two Chocolates?

It ensures selecting the two cheapest chocolates first, minimizing the sum while checking that the money constraint is satisfied.

What if I cannot afford any two chocolates?

Return the original money amount, as no valid purchase exists without going into debt.

Do I need to sort the prices array?

Sorting is optional but helps quickly identify the two cheapest chocolates for the greedy approach.

Can leftover money be zero?

Yes, if the sum of the two cheapest chocolates equals the available money, leftover is zero.

What is the time complexity of this solution?

Finding the two cheapest prices takes O(n) time and O(1) space; sorting increases time to O(n log n) if used.

terminal

Solution

Solution 1: Sorting

We can sort the prices of the chocolates in ascending order, and then add the first two prices to get the minimum cost $cost$ of buying two chocolates. If this cost is greater than the money we have, then we return `money`. Otherwise, we return `money - cost`.

1

2

3

4

5

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        prices.sort()
        cost = prices[0] + prices[1]
        return money if money < cost else money - cost

Solution 2: One-pass Traversal

We can find the two smallest prices in one pass, and then calculate the cost.

1

2

3

4

5

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        prices.sort()
        cost = prices[0] + prices[1]
        return money if money < cost else money - cost

Continue Practicing

#2708 maximum strength of a group #2659 make array empty #2790 maximum number of groups with increasing length