Buy Two Chocolates solution and explanation
Google
9 more videos on this problem
Buy Two Chocolates - Leetcode 2706 - PythonNeetCodeIO · 6:35 · 9K views
Buy Two Chocolates | Leetcode 2706codestorywithMIK · 6:51 · 5K views
2706. Buy Two Chocolates | 4 Ways | One Pass | time - O(n) & Space - O(1)Aryan Mittal · 13:05 · 1K views
Buy Two Chocolates - LeetCode #2706 - Python, JavaScript, Java and C++CodingNinja · 5:15 · 884 views
Buy Two Chocolates | Leetcode 2706 | BiWeekly 105Tech Courses · 3:26 · 830 views
Leetcode | 2706. Buy Two Chocolates | Easy | Java Solution [2 Methods]Developer Docs · 5:30 · 485 views
✅ Buy Two Chocolates - No Sorting - All Pairs - LeetCode 2706 - Explained - ArraysLeet Logics · 5:13 · 437 views
2706. Buy Two Chocolates (Leetcode Easy)Programming Live with Larry · 2:41 · 340 views
Solving LeetCode 2706 Buy Two Chocolates | Array | Amazon | Single PassCode Harmony · 7:31 · 243 views
Daily Leetcode #1359: Dec 20, 2023 - 2706. Buy Two ChocolatesProgramming Live with Larry · 2:24 · 107 views
The problem
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,2,2], money = 3 Output: 0 Explanation: Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 - 3 = 0 units of money afterwards. Thus, we return 0.
Example 2:
Input: prices = [3,2,3], money = 3 Output: 3 Explanation: You cannot buy 2 chocolates without going in debt, so we return 3.
Constraints:
2 <= prices.length <= 501 <= prices[i] <= 1001 <= money <= 100
Approach overview
Problem Overview: You are given an array prices where each value represents the cost of a chocolate, and an integer money. You must buy exactly two chocolates if their combined price does not exceed the available money. If you can afford them, return the remaining money; otherwise return the original amount.
Approach 1: Brute Force Combination Check (Time: O(n2), Space: O(1))
The straightforward approach checks every possible pair of chocolates. Use two nested loops to iterate through all index pairs (i, j) where i < j. For each pair, compute prices[i] + prices[j] and track the minimum total cost that does not exceed money. This method guarantees the correct answer because it evaluates every combination. The drawback is quadratic time complexity, which becomes inefficient as the array grows. It mainly demonstrates the core logic before optimizing.
Approach 2: Sorting and Two-Pointer Technique (Time: O(n log n), Space: O(1) or O(log n) depending on sort)
A more efficient strategy sorts the array of prices first. After sorting, the two cheapest chocolates appear at the beginning of the list. Instead of testing all combinations, compute the sum of the first two elements. If their total cost is less than or equal to money, return money - (prices[0] + prices[1]); otherwise return money. Sorting transforms the search problem into a simple lookup. The reasoning is greedy: buying the two cheapest chocolates minimizes total spending. This approach relies on concepts from sorting and greedy algorithms.
Alternative Insight: Linear Greedy Scan (Time: O(n), Space: O(1))
You can avoid sorting by scanning the array once while tracking the smallest and second-smallest prices. Update these values during iteration using simple comparisons. After the scan, check if their sum fits within the budget. This achieves optimal linear time while maintaining constant memory.
Recommended for interviews: Start with the brute force idea to show you understand the requirement of checking chocolate pairs. Then move to the greedy observation that only the two smallest prices matter. Most interviewers expect either the sorting approach or the linear scan optimization because both demonstrate clear reasoning about array traversal and minimizing cost.
Approach 1: Approach 1: Sorting and Two-Pointer Technique
Sort the array of prices and use a two-pointer technique to find the two cheapest chocolates that can be bought such that their sum is less than or equal to the given amount of money. This approach helps efficiently find a solution by reducing the problem space through sorting.
def buy_two_chocolates(prices, money):
prices.sort()
left, right = 0, len(prices) - 1
min_spent = float('inf')
while left < right:
sum_ = prices[left] + prices[right]
if sum_ <= money:
min_spent = sum_
left += 1
else:
right -= 1
return money if min_spent == float('inf') else money - min_spent
prices = [1, 2, 2]
money = 3
print(buy_two_chocolates(prices, money))import java.util.Arrays;
public class BuyChocolates {
public static int buyTwoChocolates(int[] prices, int money) {
Arrays.sort(prices);
int left = 0, right = prices.length - 1;
int minSpent = Integer.MAX_VALUE;
while (left < right) {
int sum = prices[left] + prices[right];
if (sum <= money) {
minSpent = sum;
left++;
} else {
right--;
}
}
return (minSpent == Integer.MAX_VALUE) ? money : money - minSpent;
}
public static void main(String[] args) {
int[] prices = {1, 2, 2};
int money = 3;
System.out.println(buyTwoChocolates(prices, money));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int buyTwoChocolates(std::vector<int>& prices, int money) {
std::sort(prices.begin(), prices.end());
int left = 0, right = prices.size() - 1;
int minSpent = INT_MAX;
while (left < right) {
int sum = prices[left] + prices[right];
if (sum <= money) {
minSpent = sum;
left++;
} else {
right--;
}
}
return (minSpent == INT_MAX) ? money : money - minSpent;
}
int main() {
std::vector<int> prices = {1, 2, 2};
int money = 3;
std::cout << buyTwoChocolates(prices, money) << std::endl;
return 0;
}function buyTwoChocolates(prices, money) {
prices.sort((a, b) => a - b);
let left = 0, right = prices.length - 1;
let minSpent = Infinity;
while (left < right) {
const sum = prices[left] + prices[right];
if (sum <= money) {
minSpent = sum;
left++;
} else {
right--;
}
}
return minSpent === Infinity ? money : money - minSpent;
}
console.log(buyTwoChocolates([1, 2, 2], 3));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int buyTwoChocolates(int* prices, int pricesSize, int money) {
qsort(prices, pricesSize, sizeof(int), compare);
int left = 0, right = pricesSize - 1;
int minSpent = INT_MAX;
while (left < right) {
int sum = prices[left] + prices[right];
if (sum <= money) {
minSpent = sum;
left++;
} else {
right--;
}
}
return (minSpent == INT_MAX) ? money : money - minSpent;
}
int main() {
int prices[] = {1, 2, 2};
int money = 3;
printf("%d\n", buyTwoChocolates(prices, 3, money));
return 0;
}using System;
class Program {
public static int BuyTwoChocolates(int[] prices, int money) {
Array.Sort(prices);
int left = 0, right = prices.Length - 1;
int minSpent = int.MaxValue;
while (left < right) {
int sum = prices[left] + prices[right];
if (sum <= money) {
minSpent = sum;
left++;
} else {
right--;
}
}
return (minSpent == int.MaxValue) ? money : money - minSpent;
}
static void Main() {
int[] prices = { 1, 2, 2 };
int money = 3;
Console.WriteLine(BuyTwoChocolates(prices, money));
}
}The Python implementation sorts the list and uses two pointers to identify the minimal viable pair of chocolates. Depending on sums, the function calculates leftover money.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1) for in-place operations.
Approach 2: Approach 2: Brute Force Combination Check
In this approach, check all possible pairs of chocolate prices. If a pair's sum is within the available money and minimal, update the result. Although this approach is less efficient, it is a simple and direct way to solve the problem given the constraints.
def buy_two_chocolates(prices, money):
min_spent = money + 1
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
sum_ = prices[i] + prices[j]
if sum_ <= money and sum_ < min_spent:
min_spent = sum_
return money if min_spent > money else money - min_spent
prices = [3, 2, 3]
money = 3
print(buy_two_chocolates(prices, money))public class BuyChocolates {
public static int buyTwoChocolates(int[] prices, int money) {
int minSpent = money + 1;
for (int i = 0; i < prices.length; ++i) {
for (int j = i + 1; j < prices.length; ++j) {
int sum = prices[i] + prices[j];
if (sum <= money && sum < minSpent) {
minSpent = sum;
}
}
}
return (minSpent > money) ? money : money - minSpent;
}
public static void main(String[] args) {
int[] prices = {3, 2, 3};
int money = 3;
System.out.println(buyTwoChocolates(prices, money));
}
}#include <iostream>
#include <vector>
#include <climits>
int buyTwoChocolates(std::vector<int>& prices, int money) {
int minSpent = money + 1;
for (size_t i = 0; i < prices.size(); ++i) {
for (size_t j = i + 1; j < prices.size(); ++j) {
int sum = prices[i] + prices[j];
if (sum <= money && sum < minSpent) {
minSpent = sum;
}
}
}
return (minSpent > money) ? money : money - minSpent;
}
int main() {
std::vector<int> prices = {3, 2, 3};
int money = 3;
std::cout << buyTwoChocolates(prices, money) << std::endl;
return 0;
}function buyTwoChocolates(prices, money) {
let minSpent = money + 1;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
const sum = prices[i] + prices[j];
if (sum <= money && sum < minSpent) {
minSpent = sum;
}
}
}
return minSpent > money ? money : money - minSpent;
}
console.log(buyTwoChocolates([3, 2, 3], 3));#include <stdio.h>
int buyTwoChocolates(int* prices, int pricesSize, int money) {
int minSpent = money + 1;
for (int i = 0; i < pricesSize; i++) {
for (int j = i + 1; j < pricesSize; j++) {
int sum = prices[i] + prices[j];
if (sum <= money && sum < minSpent) {
minSpent = sum;
}
}
}
return (minSpent > money) ? money : money - minSpent;
}
int main() {
int prices[] = {3, 2, 3};
int money = 3;
printf("%d\n", buyTwoChocolates(prices, 3, money));
return 0;
}using System;
class Program {
public static int BuyTwoChocolates(int[] prices, int money) {
int minSpent = money + 1;
for (int i = 0; i < prices.Length; i++) {
for (int j = i + 1; j < prices.Length; j++) {
int sum = prices[i] + prices[j];
if (sum <= money && sum < minSpent) {
minSpent = sum;
}
}
}
return (minSpent > money) ? money : money - minSpent;
}
static void Main() {
int[] prices = { 3, 2, 3 };
int money = 3;
Console.WriteLine(BuyTwoChocolates(prices, money));
}
}The brute force Python solution checks possible chocolate pairs to determine minimal spending that fits the budget, iterating via nested loops.
Time Complexity: O(n^2) because all pairs are checked.
Space Complexity: O(1), only essential tracking variables used.
Approach 3: Sorting
We can sort the prices of the chocolates in ascending order, and then add the first two prices to get the minimum cost cost of buying two chocolates. If this cost is greater than the money we have, then we return money. Otherwise, we return money - cost.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array prices.
function buyChoco(prices: number[], money: number): number {
prices.sort((a, b) => a - b);
const cost = prices[0] + prices[1];
return money < cost ? money : money - cost;
}func buyChoco(prices []int, money int) int {
sort.Ints(prices)
cost := prices[0] + prices[1]
if money < cost {
return money
}
return money - cost
}impl Solution {
pub fn buy_choco(mut prices: Vec<i32>, money: i32) -> i32 {
prices.sort();
let cost = prices[0] + prices[1];
if cost > money {
return money;
}
money - cost
}
}Approach 4: One-pass Traversal
We can find the two smallest prices in one pass, and then calculate the cost.
The time complexity is O(n), where n is the length of the array prices. The space complexity is O(1).
function buyChoco(prices: number[], money: number): number {
let [a, b] = [1000, 1000];
for (const x of prices) {
if (x < a) {
b = a;
a = x;
} else if (x < b) {
b = x;
}
}
const cost = a + b;
return money < cost ? money : money - cost;
}func buyChoco(prices []int, money int) int {
a, b := 1001, 1001
for _, x := range prices {
if x < a {
a, b = x, a
} else if x < b {
b = x
}
}
cost := a + b
if money < cost {
return money
}
return money - cost
}impl Solution {
pub fn buy_choco(prices: Vec<i32>, money: i32) -> i32 {
let mut a = 1000;
let mut b = 1000;
for &x in prices.iter() {
if x < a {
b = a;
a = x;
} else if x < b {
b = x;
}
}
let cost = a + b;
if money < cost {
money
} else {
money - cost
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Two-Pointer Technique | Time Complexity: O(n log n) for sorting. |
| Approach 2: Brute Force Combination Check | Time Complexity: O(n^2) because all pairs are checked. |
| Sorting | – |
| One-pass Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Combination Check | O(n^2) | O(1) | Useful for explaining the baseline idea or when the array size is very small |
| Sorting + Two Cheapest (Greedy) | O(n log n) | O(1) to O(log n) | Simple implementation when sorting is acceptable and you want clear greedy logic |
| Linear Scan for Two Minimums | O(n) | O(1) | Optimal approach when performance matters and sorting overhead should be avoided |
Frequently asked questions
Is Buy Two Chocolates easy or hard?
Buy Two Chocolates is categorized as an Easy problem on LeetCode with an acceptance rate above 60%. The task mainly tests basic array handling, sorting, and greedy reasoning rather than complex algorithms.
Buy Two Chocolates Python/Java solution
In Python or Java, the common solution sorts the prices array and checks the sum of the first two elements. If their sum is less than or equal to the available money, return the remaining amount; otherwise return the original money. This implementation runs in O(n log n) time due to sorting.
How to solve Buy Two Chocolates in O(n)?
Iterate through the array once while maintaining two variables: the smallest price and the second smallest price. Update them whenever a smaller value is found. After the scan, compute their sum and compare it with the available money. If the sum is affordable, return the remaining money; otherwise return the original amount.
What is the best approach for Buy Two Chocolates?
The optimal idea is to find the two smallest prices and check if their sum is within the available money. This can be done with a single linear scan that tracks the smallest and second smallest values, giving O(n) time and O(1) space complexity. Many implementations also use sorting and pick the first two elements, which runs in O(n log n) time but is simpler to implement.
Is Buy Two Chocolates asked at Google/Amazon/Meta?
Buy Two Chocolates is an easy-level array and greedy problem commonly used in coding practice platforms and interview preparation sets. While it is not known as a frequent Google or Meta interview question, similar problems involving finding minimum elements or greedy choices appear in many technical interviews.
What data structure is used in Buy Two Chocolates?
The problem primarily uses an array to store chocolate prices. Solutions rely on simple array traversal, sorting algorithms, or a greedy scan to track the smallest elements. No advanced data structures are required.
What is the time complexity of Buy Two Chocolates?
The brute force solution checks all pairs of chocolates and runs in O(n^2) time. A more efficient method sorts the price array and evaluates the two cheapest items in O(n log n) time. The optimal greedy scan tracks the two smallest prices in a single pass, achieving O(n) time and O(1) space.