You are given an integer array prices representing the prices of various chocolates in a store. You are also given a single integer money, which represents your initial amount of money.
You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.
Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return money. Note that the leftover must be non-negative.
Example 1:
Input: prices = [1,2,2], money = 3 Output: 0 Explanation: 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 Explanation: You cannot buy 2 chocolates without going in debt, so we return 3.
Constraints:
2 <= prices.length <= 501 <= prices[i] <= 1001 <= money <= 100Problem Overview: You are given an array prices where each value represents the cost of a chocolate, and an integer money. You must buy exactly two chocolates if their combined price does not exceed the available money. If you can afford them, return the remaining money; otherwise return the original amount.
Approach 1: Brute Force Combination Check (Time: O(n2), Space: O(1))
The straightforward approach checks every possible pair of chocolates. Use two nested loops to iterate through all index pairs (i, j) where i < j. For each pair, compute prices[i] + prices[j] and track the minimum total cost that does not exceed money. This method guarantees the correct answer because it evaluates every combination. The drawback is quadratic time complexity, which becomes inefficient as the array grows. It mainly demonstrates the core logic before optimizing.
Approach 2: Sorting and Two-Pointer Technique (Time: O(n log n), Space: O(1) or O(log n) depending on sort)
A more efficient strategy sorts the array of prices first. After sorting, the two cheapest chocolates appear at the beginning of the list. Instead of testing all combinations, compute the sum of the first two elements. If their total cost is less than or equal to money, return money - (prices[0] + prices[1]); otherwise return money. Sorting transforms the search problem into a simple lookup. The reasoning is greedy: buying the two cheapest chocolates minimizes total spending. This approach relies on concepts from sorting and greedy algorithms.
Alternative Insight: Linear Greedy Scan (Time: O(n), Space: O(1))
You can avoid sorting by scanning the array once while tracking the smallest and second-smallest prices. Update these values during iteration using simple comparisons. After the scan, check if their sum fits within the budget. This achieves optimal linear time while maintaining constant memory.
Recommended for interviews: Start with the brute force idea to show you understand the requirement of checking chocolate pairs. Then move to the greedy observation that only the two smallest prices matter. Most interviewers expect either the sorting approach or the linear scan optimization because both demonstrate clear reasoning about array traversal and minimizing cost.
Sort the array of prices and use a two-pointer technique to find the two cheapest chocolates that can be bought such that their sum is less than or equal to the given amount of money. This approach helps efficiently find a solution by reducing the problem space through sorting.
The array is sorted, and two pointers are used to traverse the array. The goal is to find two minimal-priced chocolates within the budget. Adjusting pointers appropriately allows us to find the correct pair, and calculation of remaining money is straightforward. If no valid pair is found, the function returns the original amount of money.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the sorting is in-place.
In this approach, check all possible pairs of chocolate prices. If a pair's sum is within the available money and minimal, update the result. Although this approach is less efficient, it is a simple and direct way to solve the problem given the constraints.
Iterate through each possible pair in the prices array using two for loops. If a pair is more affordable than previously found and within budget, update the tracking minimum.
Time Complexity: O(n^2) due to the nested loop.
Space Complexity: O(1) with a few extra variables.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Two-Pointer Technique | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Brute Force Combination Check | Time Complexity: O(n^2) due to the nested loop. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Combination Check | O(n^2) | O(1) | Useful for explaining the baseline idea or when the array size is very small |
| Sorting + Two Cheapest (Greedy) | O(n log n) | O(1) to O(log n) | Simple implementation when sorting is acceptable and you want clear greedy logic |
| Linear Scan for Two Minimums | O(n) | O(1) | Optimal approach when performance matters and sorting overhead should be avoided |
Buy Two Chocolates - Leetcode 2706 - Python • NeetCodeIO • 9,352 views views
Watch 9 more video solutions →Practice Buy Two Chocolates with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor