Buy Two Chocolates

How it works

We can find the two cheapest chocolates in a single pass without sorting. As we iterate through the prices, we maintain the two smallest values seen so far. This gives us the optimal pair to buy.

Steps

1. Initialize two variables to track the smallest (min1) and second smallest (min2) prices, both set to infinity.
2. Iterate through each price:
   • If the current price is less than min1, update min2 to be the old min1, and min1 to be the current price.
   • Otherwise, if the current price is less than min2, update min2 to be the current price.
3. Calculate the leftover money after buying chocolates at min1 and min2 prices.
4. If leftover is non-negative, return it; otherwise, return the original money.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Returning Leftover When You Cannot Afford Both Chocolates

If the sum of the two cheapest chocolates exceeds your money, you should return the original money (buy nothing), not a negative leftover or zero.

Not Updating Both Minimums Correctly

When finding a new smallest price, forgetting to shift the old minimum to become the second minimum loses track of valid candidates.

class Solution:
    def buyChoco(self, prices: list[int], money: int) -> int:
        min1 = min2 = float('inf')

        for p in prices:
            if p < min1:
                min1, min2 = p, min1
            elif p < min2:
                min2 = p

        leftover = money - min1 - min2
        return leftover if leftover >= 0 else money

class Solution {
public:
    int buyChoco(vector<int>& prices, int money) {
        int min1 = INT_MAX, min2 = INT_MAX;

        for (int p : prices) {
            if (p < min1) {
                min2 = min1;
                min1 = p;
            } else if (p < min2) {
                min2 = p;
            }
        }

        int leftover = money - min1 - min2;
        return leftover >= 0 ? leftover : money;
    }
};