Buy Two Chocolates

easy array greedy sorting

Problem

You have money units of cash and an array prices of chocolate prices. You must buy exactly two chocolates so that the leftover money stays non-negative, while minimizing the sum you pay. Return the leftover money after buying the cheapest affordable pair; if no pair is affordable, return money unchanged.

Inputprices = [1, 2, 2], money = 3

Output0

Cheapest two cost 1 + 2 = 3 ≤ 3, so leftover = 3 − 3 = 0.

prices (comma-separated)

money

def buyChoco(prices, money):
    min1 = min2 = float('inf')        # two cheapest prices so far
    for p in prices:
        if p < min1:                  # new cheapest: shift old min1 down
            min2 = min1
            min1 = p
        elif p < min2:                # new second cheapest
            min2 = p
    cost = min1 + min2                # cheapest pair total
    if cost <= money:                 # affordable -> spend it
        return money - cost
    return money                      # cannot afford any pair

function buyChoco(prices, money) {
  let min1 = Infinity, min2 = Infinity;   // two cheapest prices so far
  for (const p of prices) {
    if (p < min1) {                        // new cheapest: shift old min1 down
      min2 = min1;
      min1 = p;
    } else if (p < min2) {                 // new second cheapest
      min2 = p;
    }
  }
  const cost = min1 + min2;               // cheapest pair total
  if (cost <= money) return money - cost; // affordable -> spend it
  return money;                           // cannot afford any pair
}

int buyChoco(int[] prices, int money) {
    int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE; // two cheapest
    for (int p : prices) {
        if (p < min1) {                    // new cheapest: shift old min1 down
            min2 = min1;
            min1 = p;
        } else if (p < min2) {             // new second cheapest
            min2 = p;
        }
    }
    int cost = min1 + min2;                // cheapest pair total
    if (cost <= money) return money - cost; // affordable -> spend it
    return money;                          // cannot afford any pair
}

int buyChoco(vector<int>& prices, int money) {
    int min1 = INT_MAX, min2 = INT_MAX;    // two cheapest prices so far
    for (int p : prices) {
        if (p < min1) {                     // new cheapest: shift old min1 down
            min2 = min1;
            min1 = p;
        } else if (p < min2) {              // new second cheapest
            min2 = p;
        }
    }
    int cost = min1 + min2;                // cheapest pair total
    if (cost <= money) return money - cost; // affordable -> spend it
    return money;                          // cannot afford any pair
}

Explanation

To minimize what you spend on two chocolates, you simply buy the two cheapest ones. Any other pair costs at least as much, so this greedy choice is always optimal.

You do not even need to sort the array. A single pass tracks the smallest price min1 and the second-smallest price min2. When a new price p is below min1, the old min1 becomes the new second place and p takes first; otherwise if p beats only min2, it updates second place alone.

After the scan, cost = min1 + min2 is the cheapest possible pair total. If cost ≤ money you can afford it and the leftover is money - cost, which is guaranteed non-negative. If even the cheapest pair exceeds your budget, no valid purchase exists, so you keep all your money.

Example: prices = [1, 2, 2], money = 3. The two cheapest are 1 and 2, costing 3. Since 3 ≤ 3, the leftover is 0. For prices = [3, 2, 3], money = 3, the cheapest pair is 2 + 3 = 5 > 3, so we return 3 unchanged.

Time: O(n) Space: O(1)