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 <= 100Sort 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Buy Two Chocolates - Leetcode 2706 - Python • NeetCodeIO • 8,737 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