Buy Two Chocolates
EasyPrompt
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 <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible pair of chocolates. It uses nested loops to iterate through all combinations of two distinct chocolates, calculates their combined price, and keeps track of the minimum sum found.
Algorithm
- Initialize a variable
minCostto a very large value (e.g.,Integer.MAX_VALUE). - Use a nested loop to iterate through all unique pairs of chocolates. The outer loop runs from index
i = 0ton-1and the inner loop fromj = i + 1ton-1. - For each pair
(prices[i], prices[j]), calculate their sum,cost. - Update
minCostto be the minimum of its current value andcost. - After iterating through all pairs,
minCostwill hold the sum of the two cheapest chocolates. - If
minCostis less than or equal tomoney, it means we can afford the two cheapest chocolates. Returnmoney - minCost. - Otherwise, we cannot afford any pair of two chocolates, so we return the original
money.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. We can find the minimum cost of two chocolates by comparing the cost of every possible pair. We initialize a variable, minCost, to a very large number. Then, we use a first loop to pick one chocolate and a second, nested loop to pick another chocolate, ensuring we don't pick the same one twice. For each pair, we sum their prices. If this sum is smaller than our current minCost, we update minCost. After checking all pairs, minCost will hold the lowest possible price for two chocolates. Finally, we check if this minCost is within our budget (<= money). If it is, we return the leftover money, money - minCost. If not, we return the original money as we cannot make a purchase.
class Solution { public int buyChoco(int[] prices, int money) { int minCost = Integer.MAX_VALUE; int n = prices.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int cost = prices[i] + prices[j]; if (cost < minCost) { minCost = cost; } } } if (minCost <= money) { return money - minCost; } else { return money; } }}Complexity
Time
O(n^2), where `n` is the number of chocolates. The nested loops result in a quadratic number of comparisons.
Space
O(1), as it only requires a few variables to store the minimum cost and loop indices, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to find the correct answer.
Cons
Highly inefficient for large input arrays due to its O(n^2) time complexity.
Performs many redundant calculations as it considers every single pair.
Solutions
Solution
class Solution {public int buyChoco(int[] prices, int money) { Arrays.sort(prices); int cost = prices[0] + prices[1]; return money < cost ? money : money - cost; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.