LeetCode 2706 - Buy Two Chocolates

LeetCode Problem 2706

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem is asking us to purchase exactly two chocolates from a store given their individual prices, while ensuring that after buying them we do not end up in debt. The input consists of an array prices, where each element represents the cost of one chocolate, and an integer money, which is the total money available for spending. The output is the remaining money after buying the two chocolates such that their combined cost is minimized. If it is impossible to buy two chocolates without exceeding money, the output should be the initial money since no purchase can occur.

The constraints tell us that the array is small (2 <= prices.length <= 50) and each price as well as the money is within the range 1 to 100. This means we do not need extremely optimized solutions, and a solution with a complexity of O(n log n) or even O(n²) is feasible given the small input size. Important edge cases include when the two cheapest chocolates are still too expensive for the money available, or when multiple chocolates have the same minimum price. The problem guarantees at least two chocolates, so we do not need to handle empty arrays or arrays with a single element.

Approaches

The brute-force approach involves examining all pairs of chocolates, summing their prices, and keeping track of the minimum sum that does not exceed money. This is guaranteed to work because it explores all possible valid purchases, but it has a time complexity of O(n²) since we are checking all pairs.

The optimal approach uses the observation that to minimize the sum of two chocolates, we only need the two cheapest chocolates in the array. Sorting the array allows us to directly pick the two smallest prices, sum them, and check if that sum is less than or equal to money. This reduces the number of operations significantly compared to checking all pairs. Since sorting is O(n log n), this is efficient for our constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks all pairs of chocolates to find the minimum sum within budget
Optimal	O(n log n)	O(1)	Sorts the prices and picks the two smallest values to compute leftover money

Algorithm Walkthrough

1. Sort the array of prices in ascending order. Sorting allows us to quickly identify the cheapest chocolates.
2. Select the two smallest prices. After sorting, the first two elements of the array are the smallest.
3. Compute their sum. This sum represents the minimum cost to buy two chocolates.
4. Compare the sum with available money. If the sum is less than or equal to money, return money - sum as the leftover money.
5. Handle the insufficient funds case. If the sum exceeds money, return money because no purchase can occur without going negative.

Why it works: Sorting guarantees that the first two elements are the minimum prices. Adding them gives the smallest possible total for two chocolates, ensuring the leftover money is maximized while still buying exactly two chocolates. This method efficiently checks feasibility while minimizing the purchase cost.

Python Solution

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

Explanation: The code first sorts the prices list so that the cheapest chocolates are at the front. It then calculates the sum of the first two elements, which represents the minimum cost of buying two chocolates. If this sum does not exceed money, it returns the leftover money after purchase. Otherwise, it returns money because the purchase cannot be made.

Go Solution

import "sort"

func buyChoco(prices []int, money int) int {
    sort.Ints(prices)
    totalCost := prices[0] + prices[1]
    if totalCost <= money {
        return money - totalCost
    }
    return money
}

Explanation: In Go, we use the standard library sort.Ints to sort the slice. The two smallest prices are then summed and compared against money. The logic mirrors the Python solution. No special handling is needed for empty slices because the constraints guarantee at least two chocolates.

Worked Examples

Example 1: prices = [1,2,2], money = 3

After sorting: [1, 2, 2]

Two smallest prices: 1 + 2 = 3

Compare with money: 3 <= 3 → leftover: 3 - 3 = 0

Example 2: prices = [3,2,3], money = 3

After sorting: [2, 3, 3]

Two smallest prices: 2 + 3 = 5

Compare with money: 5 > 3 → leftover: 3

Step	prices	two smallest sum	money comparison	leftover
1	[1,2,2]	3	3 <= 3	0
2	[2,3,3]	5	5 > 3	3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1)	Sorting can be done in-place; only a few variables used

Sorting is the dominant factor in time complexity. Space usage is minimal since we only use a few extra variables, and in Python/Go, the sort can be in-place.

Test Cases

# Provided examples
assert Solution().buyChoco([1,2,2], 3) == 0  # minimal leftover
assert Solution().buyChoco([3,2,3], 3) == 3  # cannot buy two

# Edge cases
assert Solution().buyChoco([1,1], 10) == 8  # cheapest chocolates much less than money
assert Solution().buyChoco([5,5,5], 10) == 0  # exactly enough for two
assert Solution().buyChoco([100,100], 50) == 50  # cannot afford any
assert Solution().buyChoco([2,2,2,2], 4) == 0  # multiple identical cheap options
assert Solution().buyChoco([1,2,3,4,5], 3) == 0  # minimum two sum equals money

Test	Why
[1,2,2], 3	verifies minimal leftover calculation
[3,2,3], 3	verifies behavior when purchase impossible
[1,1], 10	tests leftover when cheap options available
[5,5,5], 10	tests exact fit scenario
[100,100], 50	tests unable to buy scenario
[2,2,2,2], 4	verifies handling of duplicates
[1,2,3,4,5], 3	confirms selection of two cheapest even with larger array

Edge Cases

All chocolates too expensive: If the sum of the two cheapest chocolates exceeds money, we must return money because no purchase is possible. This prevents negative leftovers and ensures correctness.

Multiple chocolates with the same minimum price: The solution handles duplicates naturally due to sorting. It will always pick the first two elements, which could be the same, ensuring minimal cost.

Exact fit to money: When the two cheapest chocolates sum exactly to money, the leftover becomes zero. The solution correctly computes this by subtracting the sum from money only if the total is less than or equal to money.