Buy Two Chocolates

Difficulty: Easy | Acceptance: 68.30% | Paid: No Topics: Array, Greedy, Sorting

You are given an integer array prices representing the prices of chocolates in a store. You are also given an integer money representing the amount of money you have.

You would like to buy two chocolates to maximize the amount of money you have left. Return the amount of money you will have leftover after buying the two chocolates. If you cannot afford two chocolates, return money.

Note that you must buy two chocolates.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Sorting
• Approach 3: Single Pass

Examples

Example 1:

Input: prices = [1,2,2], money = 3
Output: 0
Explanation: You can buy chocolates at indices 1 and 2 with a total cost of 2. 
Your leftover money is 3 - 2 = 0.

Example 2:

Input: prices = [3,2,3], money = 3
Output: 3
Explanation: You cannot buy two chocolates without going over your budget, so you return 3.

Constraints

2 <= prices.length <= 50
1 <= prices[i] <= 100
1 <= money <= 100

Approach 1: Brute Force

Intuition Check every possible pair of chocolates to find the minimum cost that is less than or equal to the available money.

Steps

• Initialize min_cost to infinity.
• Iterate through the array with two nested loops to consider every pair (i, j) where i < j.
• Calculate the sum of the pair.
• If the sum is less than or equal to money and less than the current min_cost, update min_cost.
• If min_cost was updated (meaning a valid pair was found), return money - min_cost. Otherwise, return money.

from typing import List

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        min_cost = float('inf')
        n = len(prices)
        for i in range(n):
            for j in range(i + 1, n):
                current_cost = prices[i] + prices[j]
                if current_cost <= money and current_cost < min_cost:
                    min_cost = current_cost
        
        if min_cost != float('inf'):
            return money - min_cost
        return money

Complexity

• Time: O(n²) where n is the number of chocolates.
• Space: O(1)
• Notes: Simple but inefficient for large inputs.

Approach 2: Sorting

Intuition The two cheapest chocolates will be the first two elements if the array is sorted in ascending order.

Steps

• Sort the prices array in ascending order.
• Calculate the sum of the first two elements (prices[0] + prices[1]).
• If the sum is less than or equal to money, return money - sum.
• Otherwise, return money.

from typing import List

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        prices.sort()
        total_cost = prices[0] + prices[1]
        if total_cost <= money:
            return money - total_cost
        return money

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(1) or O(n) depending on the sorting algorithm’s implementation.
• Notes: More efficient than brute force, but sorting is not strictly necessary since we only need the two smallest values.

Approach 3: Single Pass

Intuition We can find the two smallest values in a single iteration without sorting the entire array.

Steps

• Initialize two variables, min1 and min2, to infinity (or a very large number).
• Iterate through each price in the array:
  • If the current price is less than min1, update min2 to be min1, and then update min1 to be the current price.
  • Else if the current price is less than min2, update min2 to be the current price.
• After the loop, calculate the sum of min1 and min2.
• If the sum is less than or equal to money, return money - sum.
• Otherwise, return money.

from typing import List

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        min1 = float('inf')
        min2 = float('inf')
        for p in prices:
            if p < min1:
                min2 = min1
                min1 = p
            elif p < min2:
                min2 = p
        total_cost = min1 + min2
        if total_cost <= money:
            return money - total_cost
        return money

Complexity

• Time: O(n) where n is the number of chocolates.
• Space: O(1)
• Notes: This is the optimal approach as it requires only one pass through the array and constant extra space.