2706. Buy Two Chocolates

Problem Description

In this problem, you have an array prices that consists of the prices of chocolates available in a store. Additionally, you have an integer money that represents the amount of money you initially have. Your goal is to purchase exactly two chocolates. The two chocolates you choose to buy must cost less than or equal to the money you have. The objective is not just to find any two chocolates that you can afford but to select two such that you minimize the sum of their prices. By doing this, you maximize the amount of money you will have left after the purchase. The problem asks you to return the amount of money that will remain after buying these two chocolates. If it is not possible to buy two chocolates without spending more money than you have (that is, without going into debt), you need to return the original amount of money.

Intuition

The intuition behind the solution is to first sort the array of prices in ascending order. Sorting ensures that the chocolates with the lowest prices come first. To minimize the sum of the prices of the two chocolates, you simply need to choose the first two chocolates in the sorted array because they will be the cheapest.

After sorting, the algorithm checks the sum of the prices of the first two chocolates and compares it with the money you have. If the sum is less than or equal to money, it means you can afford these two chocolates and thus you should return the leftover amount, which is money - cost of the two chocolates. However, if the sum is greater than money, you cannot afford any pair of chocolates without going into debt, so the function should return the initial amount of money without any purchase, which is simply money.

In summary, the solution hinges on the fact that sorting the prices array helps identify the minimum cost for buying two chocolates. This turns the problem into a simple comparison and subtraction operation.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search can be used to find whether two components in a graph are connected.

TrueFalse

I don’t know

Solution Approach

The implementation of the solution can be dissected into few simple steps:

Sorting: First, we sort the prices array using the sort method. In Python, this is done using the sort() function. Sorting is an essential step here because it uses the built-in efficient sorting algorithms like Timsort (a hybrid sorting algorithm derived from merge sort and insertion sort) in Python. Through sorting, we can ensure that we are considering the cheapest chocolates first.
```
1prices.sort()
```
Calculating Minimum Cost: Once the array is sorted, the prices of the two cheapest chocolates can be accessed with prices[0] and prices[1]. The sum of these two prices gives us the minimum cost needed to purchase two chocolates.
```
1cost = prices[0] + prices[1]
```
Checking Affordability and Computing Leftover Money: The if-else statement is used to check if you can afford to buy the two chocolates without going into debt. This is done by comparing the money with the cost of buying the two cheapest chocolates.
- If money is less than cost, you cannot afford any two chocolates and should return the original amount of money.
- If money is greater than or equal to cost, it means you can afford the chocolates, so you return the money left after the purchase, i.e., money - cost.
```
1return money if money < cost else money - cost
```

This approach leverages the efficiency of Python's sorting function and simple arithmetic operations to achieve the solution. The time complexity of this solution is dominated by the sorting step, which is ( O(n \log n) ) where n is the number of prices in the array. The space complexity is ( O(1) ) as no additional space is used apart from the input and variables to store the cost and the final answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Example Walkthrough

Let's say we have an array prices = [5, 3, 20, 8] and money = 10. We want to buy exactly two chocolates within the money we have, and maximize the amount left after the purchase. Now let's go through the solution steps with this example:

Sorting: First, we sort the array prices. After sorting, the array becomes prices = [3, 5, 8, 20].

1prices.sort()  # prices becomes [3, 5, 8, 20]

Calculating Minimum Cost: We then calculate the cost of buying the two cheapest chocolates, which are now prices[0] and prices[1], i.e., 3 and 5.

1cost = prices[0] + prices[1]  # cost becomes 3 + 5 = 8

Checking Affordability and Computing Leftover Money: We check if the money we have is enough to cover the cost.
- We compare money (10) with cost (8). Since 10 is greater than 8, we can afford the chocolates.
- We then calculate the money left after the purchase, which is money - cost.
```
1leftover_money = money - cost  # leftover_money becomes 10 - 8 = 2
```

Therefore, with prices = [5, 3, 20, 8] and money = 10, after purchasing the two chocolates costing 3 and 5, we are left with 2 as the answer.

Using this walkthrough as a guide, it's clear that the solution approach effectively uses sorting to minimize the purchase cost and an if-else logic to ensure we don't overspend. The result, 2 in this case, represents the optimal amount of money remaining after making a legitimate purchase of two chocolates.

Solution Implementation

1# The List type needs to be imported from typing to be used as a type hint.
2from typing import List
3
4class Solution:
5    def buyChoco(self, prices: List[int], money: int) -> int:
6        # Sort the prices in non-decreasing order to find the cheapest chocolates.
7        prices.sort()
8      
9        # We check if there are at least two chocolates to buy,
10        # as the customer should buy at least two chocolates to get the discount.
11        if len(prices) < 2:
12            # If we have less than two chocolates, we can't calculate a combined cost
13            # so the customer can't spend the money on chocolates as intended.
14            return 0
15      
16        # Calculate the combined cost of the two cheapest chocolates.
17        cost = prices[0] + prices[1]
18      
19        # If the customer doesn't have enough money to buy the two cheapest chocolates,
20        # they can't make a purchase, so return 0.
21        if money < cost:
22            return 0
23      
24        # Otherwise, deduct the combined cost from the customer's money
25        # and return the remaining amount.
26        return money - cost
27

1import java.util.Arrays; // Import Arrays class for sorting
2
3class Solution {
4
5    // Method to calculate how much money is left after buying two cheapest chocolates
6    public int buyChoco(int[] prices, int money) {
7        // Sort the array to get the prices in ascending order
8        Arrays.sort(prices); 
9
10        // Calculate the cost of the two cheapest chocolates
11        int costOfTwoCheapest = prices[0] + prices[1]; 
12
13        // If the money is less than the cost of two chocolates, return the original amount of money
14        // since you can't afford to buy them. Otherwise, return the remaining money after purchase.
15        return money < costOfTwoCheapest ? money : money - costOfTwoCheapest; 
16    }
17}
18

1#include <vector>
2#include <algorithm> // Include algorithm header for using the sort function
3
4class Solution {
5public:
6    // This function calculates the remaining money after buying the two cheapest chocolates.
7    int buyChoco(vector<int>& prices, int money) {
8        // Sort the prices of the chocolates in ascending order
9        sort(prices.begin(), prices.end());
10
11        // Check if we have at least two chocolate prices
12        if (prices.size() < 2) {
13            // If not, we can't buy two chocolates, so return the original amount of money.
14            return money;
15        }
16
17        // Calculate the total cost of buying the two cheapest chocolates
18        int totalCost = prices[0] + prices[1];
19
20        // If we have enough money for at least the two cheapest chocolates, return the remaining money
21        // Otherwise, return the original amount as we can't buy those chocolates
22        return (money >= totalCost) ? (money - totalCost) : money;
23    }
24};
25

1// Defines a function to determine how much money will be left after buying the two cheapest chocolates
2// prices: Array of numbers representing the prices of different chocolates
3// money: The total amount of money available to spend
4function buyChoco(prices: number[], money: number): number {
5    // Sort the prices array in ascending order to identify the two cheapest chocolates
6    prices.sort((a, b) => a - b);
7
8    // Calculate the total cost of the two cheapest chocolates
9    const totalCostOfCheapestTwo: number = prices[0] + prices[1];
10
11    // If the total money is less than the cost of the two cheapest chocolates,
12    // return the original amount of money since no purchase can be made.
13    // Otherwise, return the remaining money after the purchase is made.
14    return money < totalCostOfCheapestTwo ? money : money - totalCostOfCheapestTwo;
15}
16

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the function buyChoco is determined primarily by the sorting operation. The sorting function in Python, .sort(), typically uses Timsort, which has an average and worst-case time complexity of O(n log n) where n is the number of elements in the list prices.

Since the rest of the operations after sorting (accessing the first two elements and basic arithmetic operations) are constant time operations, i.e., O(1), they don't significantly contribute to the overall time complexity.

Thus, the total time complexity of the function buyChoco is O(n log n).

Space Complexity

The space complexity of the function buyChoco is determined by the additional space required for the operation of the code.

Since the sorting operation is done in place with the .sort() method, it does not require any additional space proportional to the input (it uses only a constant amount of extra space).

Therefore, the space complexity is O(1), which is constant space complexity, since no additional space is allocated that scales with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructureOverlapping subproblemsNon-overlapping subproblemsConstant time subproblems

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2706. Buy Two Chocolates

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings