Scale Engineer

Buy Two Chocolates

Easy
#2441Time: 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.
Patterns
Greedy
Algorithms
Sorting
Data structures
Array

Prompt

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 <= 50
  • 1 <= prices[i] <= 100
  • 1 <= 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 minCost to 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 = 0 to n-1 and the inner loop from j = i + 1 to n-1.
  • For each pair (prices[i], prices[j]), calculate their sum, cost.
  • Update minCost to be the minimum of its current value and cost.
  • After iterating through all pairs, minCost will hold the sum of the two cheapest chocolates.
  • If minCost is less than or equal to money, it means we can afford the two cheapest chocolates. Return money - 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

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.

← Previous

Previous problem

Next →

Next problem