2706. Buy Two Chocolates - Explanation

Problem Link

Description

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,3,2], money = 5

Output: 2

Explanation: Buy the two chocolates with prices 1 + 2. The leftover money is 5 - 3 = 2.

Example 2:

Input: prices = [2,5,1,2], money = 3

Output: 0

Explanation: Buy the two chocolates with prices 1 + 2. The leftover money is 3 - 3 = 0.

Example 3:

Input: prices = [2,2,4,3], money = 2

Output: 2

Explanation: There is no way to buy two chocolates. So, we return the given money 2.

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        res = -1
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                if prices[i] + prices[j] <= money:
                    res = max(res, money - prices[i] - prices[j])
        return res if res != -1 else money

Time & Space Complexity

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

---

2. Sorting

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

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

3. Greedy

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

Time & Space Complexity

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