2819. Minimum Relative Loss After Buying Chocolates
Problem Description
In this problem, you are given an array prices
that represents the cost of chocolates and a 2D array queries
, each containing two integers: k_i
and m_i
. Alice and Bob are purchasing chocolates together, and they have a special arrangement for sharing the cost. For any given chocolate:
- If the chocolate costs less than or equal to
k_i
, then Bob will pay for it entirely. - If the chocolate costs more than
k_i
, Bob will payk_i
, and Alice will cover the remaining cost.
Bob can choose exactly m_i
chocolates, and he wants to minimize his relative loss. The relative loss is defined as the difference between the total amount Bob paid and the total amount Alice paid, which he wants to minimize.
Your task is to determine the minimum relative loss Bob can achieve for each query queries[i]
and return an array of integers representing these minimum losses.
Intuition
Given that Bob wants to minimize his relative loss (Bob's payment minus Alice's payment), we have to approach this problem by trying to minimize the expenses that go beyond Bob's contribution limit (k_i
). To achieve this, we can choose more chocolates with prices within or equal to Bob's limit and try to minimize picking chocolates that require an additional payment from Alice.
To find the optimum distribution of chocolates that Bob should pay for completely and those that Alice contributes to, we can:
- Sort the
prices
array in ascending order. This allows us to quickly identify which chocolates can be paid for by Bob and which will require a contribution from Alice. - We can use binary search to find the breakpoint where Bob should stop paying for chocolates entirely and start sharing the cost with Alice.
The function f(k, m)
performs this binary search by finding the right number of chocolates Bob can fully pay for without incurring too much additional cost from Alice. Given that m
chocolates in total need to be purchased, the function calculates the split (using a binary search approach) between the chocolates paid for entirely by Bob and those partially paid for by him (with the rest paid by Alice).
This split helps minimize Bob's relative loss, as it finds the best point where paying an equal or lesser price fully (for as many chocolates as possible) and sharing the cost of the more expensive chocolates leads to the smallest difference between Bob's payment and Alice's payment.
Finally, the minimumRelativeLosses
method calculates the minimum loss for each query by considering the split point l
, computing the total cost paid by Bob and Alice, and then determining the relative loss (Bob's payment minus Alice's payment). The result for each query is then appended to the ans
list, which is returned as the solution to the problem.
Solution Approach
The solution uses a binary search algorithm combined with a prefix sum technique to efficiently compute the required values for minimizing Alice's contribution and thus Bob's relative loss.
Here's a step-by-step breakdown:
-
First, we sort the
prices
array. This is crucial as it allows us to apply binary search later. -
We compute the prefix sums of the array using
accumulate(prices, initial=0)
. Prefix sums are efficient for calculating the sum of a subarray in constant time O(1). Having a prefix sum arrays
meanss[i]
represents the sum of the prices array fromprices[0]
toprices[i-1]
. -
The code then defines a function
f(k: int, m: int) -> int
that uses binary search to find the optimal split pointl
:-
Initialize two pointers,
l
andr
.l
starts at 0, andr
is the minimum ofm
and the index of the rightmost chocolate whose price does not exceedk
. This index is found usingbisect_right(prices, k)
which returns the insertion point to the right ofk
in the sortedprices
list. -
While
l < r
, we find the mid-point and calculate how many chocolates to the right ofmid
Bob would need to share the cost with Alice (right = m - mid
). -
If the price of the chocolate at midpoint is less than
2 * k - prices[n - right]
, we move thel
pointer tomid + 1
. This condition checks if the price at the mid is preferred over the price at the symmetric position in the second half (towards the array's end). -
If the condition is not met, we move the
r
pointer tomid
. This helps us to narrow down the split point where Bob would switch from paying in full to sharing the cost.
-
-
For each
k, m
pair inqueries
, we get the split pointl
usingf(k, m)
. Calculate Bob's total payment as the sum of the chocolate prices up tol
(s[l]
) plus doubledk
for each of the chocolates froml
tom
(2 * k * r
). Calculate Alice's total payment as the sum of the chocolate prices not covered by Bob (s[n] - s[n - r]
). -
Compute the loss as
loss = s[l] + 2 * k * r - (s[n] - s[n - r])
, which represents Bob's total payment minus Alice's total payment. -
Append each computed loss to the
ans
array, which stores Bob's minimum relative loss for each query.
By combining binary search to efficiently find the optimal split of chocolate prices Bob should pay fully, and prefix sums to quickly compute the sums for Bob's and Alice's payments, the entire algorithm remains efficient and effective at minimizing Bob's relative loss for all the queries.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider a small example to illustrate the solution approach using the following prices
array and queries
.
Suppose the prices
array is [1, 4, 5, 7, 8]
representing the cost of chocolates in ascending order. And there is one query in the queries
array: [4, 3]
which means that Bob's payment limit k_i
is 4 and he can choose m_i
= 3 chocolates.
Here are the steps we would take to find the minimum relative loss for this query:
-
Since our
prices
array is already sorted, we don't need to sort it again. -
We calculate the prefix sums of the
prices
array. The prefix sums arrays
would be[0, 1, 5, 10, 17, 25]
. -
Next, using the
f(k, m)
function, we perform a binary search to find the optimal number of chocolates that Bob will pay for entirely, without sharing the cost with Alice.Given
k
= 4 andm
= 3, we initializel
= 0 andr
= min(3, 2) since there are 2 chocolates at indices0
and1
that are less than or equal tok
.So,
r
starts at 2. We examine the midpointmid
betweenl
andr
, which is 1. Calculating the number of chocolates to the right ofmid
that Bob has to share the cost for:right = m - mid
= 3 - 1 = 2.The condition in our binary search checks if
prices[mid] < 2 * k - prices[n - right]
, which isprices[1] < 2 * 4 - prices[5 - 2]
, meaning4 < 8 - 5
. Since this is false, we don't adjustl
; instead, we maker
equal tomid
.With
l
= 0 andr
= 1, we find thatmid
= 0, and repeating the above condition, we getprices[0] < 2 * 4 - prices[5 - 2]
, which means1 < 8 - 5
. This condition is true, so we updatel
tomid + 1
, which makesl
= 1.As
l
cannot be less thanr
, our binary search concludes thatl
= 1 is the optimal split point. -
For the query
[4, 3]
, we havel
= 1 andr
=m
-l
= 2. Bob's total payment is the sum of prefix sums up tol
plusk
timesr
ors[1] + 2 * k * r
, which gives us1 + 2 * 4 * 2 = 17
. Alice's total payment iss[5] - s[5 - r] = 25 - 10 = 15
. -
The relative loss for Bob is thus
17 - 15 = 2
. We append2
to our answer array, which means for the query(4, 3)
, the minimum relative loss Bob can achieve is2
.
By going through the above steps, we conclude that by choosing the first one chocolate costing 1
(within his limit) and contributing to the costs of two more expensive chocolates (with Alice covering the remaining), Bob can minimize his relative loss to 2
.
Solution Implementation
1from bisect import bisect_right
2from typing import List
3from itertools import accumulate
4
5class Solution:
6 def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:
7 # Helper function to find the split point where we choose which paintings to buy
8 def find_split(k: int, m: int) -> int:
9 left, right = 0, min(m, bisect_right(prices, k))
10 # Binary search to find the optimal split between buying cheaper paintings
11 # and the given value painting
12 while left < right:
13 mid = (left + right) >> 1
14 remaining = m - mid
15 # Compare the mid-th price with the price that makes the total loss minimum
16 if prices[mid] < 2 * k - prices[len(prices) - remaining]:
17 left = mid + 1
18 else:
19 right = mid
20 return left
21
22 prices.sort() # Sort the list of prices
23 accumulated_prices = list(accumulate(prices, initial=0)) # Get the accumulated price sum
24 results = [] # This will store the results of our queries
25 num_prices = len(prices) # Get the number of available paintings
26
27 # Process each query
28 for value, quantity in queries:
29 split_point = find_split(value, quantity) # Find the split point based on value and quantity
30 quantity_left = split_point
31 quantity_right = quantity - split_point
32 # Calculate the total loss
33 loss = accumulated_prices[split_point] + 2 * value * quantity_right - (accumulated_prices[num_prices] - accumulated_prices[num_prices - quantity_right])
34 results.append(loss) # Append the calculated loss to results
35
36 return results
37
38# Example of how to use the class
39# solution = Solution()
40# print(solution.minimumRelativeLosses([10, 15, 20], [[15, 2], [20, 3]]))
41
1class Solution {
2 private int itemCount; // The number of items in the prices array
3 private int[] itemPrices; // Array of item prices
4
5 public long[] minimumRelativeLosses(int[] prices, int[][] queries) {
6 itemCount = prices.length;
7 Arrays.sort(prices); // Sort prices in ascending order
8 this.itemPrices = prices; // Assign sorted prices to instance variable
9 // Initialize the prefix sum array with an additional zero at the start
10 long[] prefixSum = new long[itemCount + 1];
11 for (int i = 0; i < itemCount; ++i) {
12 prefixSum[i + 1] = prefixSum[i] + prices[i];
13 }
14 int q = queries.length; // The number of queries
15 long[] answers = new long[q]; // Array to hold the answers to the queries
16 for (int i = 0; i < q; ++i) {
17 // Extract k and m from each query
18 int k = queries[i][0], m = queries[i][1];
19 // Find the optimal left index for dividing the array into two parts
20 int left = optimalLeftIndex(k, m);
21 int right = m - left; // Calculate the right part size
22 // Calculate the minimum relative loss for the query
23 answers[i] = prefixSum[left] + (2L * k * right) - (prefixSum[itemCount] - prefixSum[itemCount - right]);
24 }
25 return answers; // Return the array of answers
26 }
27
28 // Helper method to find the optimal left index
29 private int optimalLeftIndex(int k, int m) {
30 int left = 0, right = Arrays.binarySearch(itemPrices, k);
31 if (right < 0) {
32 right = -(right + 1);
33 }
34 right = Math.min(m, right);
35 while (left < right) {
36 int mid = (left + right) / 2;
37 int remainingRight = m - mid;
38 // Determine if we should move the partition to the right or left
39 if (itemPrices[mid] < 2L * k - itemPrices[itemCount - remainingRight]) {
40 left = mid + 1;
41 } else {
42 right = mid;
43 }
44 }
45 return left; // Return the optimal left index
46 }
47}
48
1#include <vector>
2#include <algorithm> // For std::sort and std::upper_bound
3
4class Solution {
5public:
6 // Function to calculate the minimum relative losses for each query.
7 vector<long long> minimumRelativeLosses(vector<int>& prices, vector<vector<int>>& queries) {
8 int n = prices.size();
9 // Sort the prices in ascending order to apply binary search later.
10 sort(prices.begin(), prices.end());
11
12 // Build a prefix sum array to quickly calculate sums of segments.
13 vector<long long> prefixSum(n + 1, 0);
14 for (int i = 1; i <= n; ++i) {
15 prefixSum[i] = prefixSum[i - 1] + prices[i - 1];
16 }
17
18 // Binary search function to find the optimal split point for the given constraints.
19 auto calculateSplitPoint = [&](int target, int maxSize) {
20 int left = 0, right = upper_bound(prices.begin(), prices.end(), target) - prices.begin();
21 right = min(right, maxSize);
22 while (left < right) {
23 int mid = (left + right) >> 1;
24 int numRight = maxSize - mid;
25 if (prices[mid] < 2LL * target - prices[n - numRight]) {
26 left = mid + 1;
27 } else {
28 right = mid;
29 }
30 }
31 return left;
32 };
33
34 // Answer vector to hold the result for each query.
35 vector<long long> ans;
36 for (auto& query : queries) {
37 int target = query[0], maxSize = query[1];
38 // Find the split point where we get the minimum relative loss.
39 int splitPoint = calculateSplitPoint(target, maxSize);
40 int numRight = maxSize - splitPoint;
41 // Calculate the loss based on the split point determined using binary search.
42 long long loss = prefixSum[splitPoint] + 2LL * target * numRight - (prefixSum[n] - prefixSum[n - numRight]);
43 ans.push_back(loss);
44 }
45 return ans;
46 }
47};
48
1function minimumRelativeLosses(prices: number[], queries: number[][]): number[] {
2 // The length of the prices array
3 const pricesLength: number = prices.length;
4 // Sort the prices array in ascending order.
5 prices.sort((a, b) => a - b);
6
7 // Create a prefix sum array to store cumulative sum of sorted prices.
8 const prefixSums: number[] = Array(pricesLength).fill(0);
9 for (let i = 0; i < pricesLength; ++i) {
10 prefixSums[i + 1] = prefixSums[i] + prices[i];
11 }
12
13 // Binary search to find the index of the first price greater than x.
14 const searchIndex = (x: number): number => {
15 let left = 0;
16 let right = pricesLength;
17 while (left < right) {
18 const mid = Math.floor((left + right) / 2);
19 if (prices[mid] > x) {
20 right = mid;
21 } else {
22 left = mid + 1;
23 }
24 }
25 return left;
26 };
27
28 // Function to find number of elements to include from start of sorted prices
29 // to minimize the loss when k items are priced at 'k' and remaining items are
30 // at their respective prices from sorted prices.
31 const findMinLossSplit = (k: number, m: number): number => {
32 let left = 0;
33 let right = Math.min(searchIndex(k), m);
34 while (left < right) {
35 const mid = Math.floor((left + right) / 2);
36 const rightCount = m - mid;
37 if (prices[mid] < 2 * k - prices[pricesLength - rightCount]) {
38 left = mid + 1;
39 } else {
40 right = mid;
41 }
42 }
43 return left;
44 };
45
46 // Main logic where for each query, it calculates the minimum relative loss.
47 const answers: number[] = [];
48 for (const [outputPrice, outputCount] of queries) {
49 const leftCount = findMinLossSplit(outputPrice, outputCount);
50 const rightCount = outputCount - leftCount;
51 answers.push(
52 prefixSums[leftCount] +
53 2 * outputPrice * rightCount -
54 (prefixSums[pricesLength] - prefixSums[pricesLength - rightCount])
55 );
56 }
57
58 // Return resulting minimum losses for all queries.
59 return answers;
60}
61
Time and Space Complexity
Time Complexity
The minimumRelativeLosses
function consists of a main for-loop that processes each query, a sorted operation on the prices list, and a helper function (f
) that uses binary search.
-
Sorting the
prices
list has a time complexity ofO(n log n)
, wheren
is the length of the prices. -
The
accumulate
function, which calculates the prefix sum arrays
, has a time complexity ofO(n)
because it processes each element in theprices
array exactly once. -
The function
f
uses a binary search to find the optimal split point that minimizes relative losses. The binary search within thef
function runs inO(log min(m, n))
, wherem
is the number of elements in one query andn
is the length of the prices. This is due to the binary search being potentially limited bym
, the number of elements that the query wants to examine. -
The main for-loop iterates over each query in
queries
. Assumingq
is the number of queries, the for-loop runsq
times. Inside this loop, thef
function is called, which has theO(log min(m, n))
complexity.
So the overall time complexity of the for-loop including the call to the f
function is O(q * log min(m, n))
.
Combining these complexities, we get O(n log n) + O(n) + O(q * log min(m, n))
. Since q * log min(m, n)
could potentially be larger than n log n
and n
, especially when q
is large, we can consider O(q * log min(m, n))
to be the dominating term in typical scenarios.
Final Time Complexity: O(n log n) + O(n) + O(q * log min(m, n))
.
Space Complexity
-
The
prices
list is sorted in-place, so no additional space is required for that. -
The
accumulate
function creates a prefix sum arrays
withn + 1
elements, giving a space complexity ofO(n)
. -
The
ans
list will holdq
elements (one for each query), which gives a space complexity ofO(q)
.
The only additional space used is the s
and ans
lists, since binary search does not require additional space beyond the few variables for pointers and indices.
Final Space Complexity: O(n) + O(q)
or simply O(n + q)
if we assume q
can be as significant as n
.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!