# Buy Two Chocolates
**Difficulty:** EASY
[External](https://leetcode.com/problems/buy-two-chocolates)
Canonical: https://scaleengineer.com/dsa/problems/buy-two-chocolates
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
        }
    }
}
```
### 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`.

## Sorting the Prices
A more optimized approach involves sorting the `prices` array first. Once sorted, the two cheapest chocolates are simply the first two elements. We can then check if their combined price is affordable.
**Time:** O(n log n), where `n` is the number of chocolates. This is dominated by the time it takes to sort the array. · **Space:** O(log n) to O(n), depending on the sorting algorithm used. Java's `Arrays.sort` for primitive types uses a variant of Quicksort, which requires O(log n) space on average for the recursion stack.
**Pros:** Much more efficient than the brute-force approach, with O(n log n) complexity.; The logic is simple and clean after the array is sorted.
**Cons:** The time complexity is dominated by the sorting algorithm, which is not as fast as a single-pass approach.; Sorting modifies the original array, which might not be desirable in some scenarios. A copy would be needed to avoid this, using extra space.
### Explanation
The logic behind this approach is that to minimize the sum of two prices, we must choose the two individually smallest prices. By sorting the `prices` array in ascending order, we ensure that the two smallest prices are located at the very beginning of the array, specifically at indices 0 and 1. We can then calculate their sum, `minCost = prices[0] + prices[1]`. This `minCost` is the absolute minimum cost for any pair of two chocolates. We then compare this `minCost` with the `money` we have. If `minCost` is less than or equal to `money`, we can afford them, and the result is `money - minCost`. If `minCost` is greater than `money`, then even the cheapest pair is too expensive, meaning no other pair (which would be even more expensive) can be bought. In that case, we return the original `money`.

```java
import java.util.Arrays;

class Solution {
    public int buyChoco(int[] prices, int money) {
        Arrays.sort(prices);
        int minCost = prices[0] + prices[1];

        if (minCost <= money) {
            return money - minCost;
        } else {
            return money;
        }
    }
}
```
### Algorithm
*   Sort the `prices` array in non-decreasing order.
*   The two cheapest chocolates will now be the first two elements of the array, `prices[0]` and `prices[1]`.
*   Calculate their sum: `cost = prices[0] + prices[1]`.
*   Check if `cost` is less than or equal to `money`.
*   If it is, return the leftover amount: `money - cost`.
*   If it's not, it's impossible to buy any two chocolates, so return the original `money`.

## Single Pass to Find Two Minimums
The most efficient approach is to find the two smallest prices in a single pass through the array, without the overhead of a full sort. This gives a linear time complexity solution.
**Time:** O(n), where `n` is the number of chocolates, because we only need to iterate through the array once. · **Space:** O(1), as we only use a constant number of extra variables to keep track of the two minimum prices.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Does not modify the input array.
**Cons:** The logic to track the two minimums can be slightly more complex to write correctly compared to the sorting approach.
### Explanation
We don't need to sort the entire array; we only need to identify the two smallest elements. This can be achieved in a single iteration. We declare two variables, `firstMin` and `secondMin`, and initialize them to a very large value. We then loop through each price in the `prices` array. For each price, we check if it's smaller than `firstMin`. If it is, the current `firstMin` becomes the `secondMin`, and the new price becomes the `firstMin`. If the price is not smaller than `firstMin` but is smaller than `secondMin`, we update `secondMin` with this price. After the loop completes, we will have the two smallest prices stored in `firstMin` and `secondMin`. The rest of the logic is the same: we sum them up, check if the sum is affordable, and return the leftover money or the original amount.

```java
class Solution {
    public int buyChoco(int[] prices, int money) {
        int firstMin = Integer.MAX_VALUE;
        int secondMin = Integer.MAX_VALUE;

        for (int price : prices) {
            if (price < firstMin) {
                secondMin = firstMin;
                firstMin = price;
            } else if (price < secondMin) {
                secondMin = price;
            }
        }

        int minCost = firstMin + secondMin;

        if (minCost <= money) {
            return money - minCost;
        } else {
            return money;
        }
    }
}
```
### Algorithm
*   Initialize two variables, `min1` and `min2`, to a value larger than any possible price (e.g., `Integer.MAX_VALUE`).
*   Iterate through the `prices` array once.
*   For each `price`:
    *   If `price` is less than `min1`, it's the new smallest. Update `min2 = min1` and `min1 = price`.
    *   Else, if `price` is less than `min2`, it's the new second-smallest. Update `min2 = price`.
*   After the loop, `min1` and `min2` will hold the two smallest prices.
*   Calculate `cost = min1 + min2`.
*   If `cost <= money`, return `money - cost`.
*   Otherwise, return `money`.

# Solutions
### Java

```java
class Solution {
public
  int buyChoco(int[] prices, int money) {
    Arrays.sort(prices);
    int cost = prices[0] + prices[1];
    return money < cost ? money : money - cost;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int buyChoco(vector<int> &prices, int money) {
    sort(prices.begin(), prices.end());
    int cost = prices[0] + prices[1];
    return money < cost ? money : money - cost;
  }
};

```

### Python

```python
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

```