You are given an integer array prices, which shows the chocolate prices and a 2D integer array queries, where queries[i] = [ki, mi].
Alice and Bob went to buy some chocolates, and Alice suggested a way to pay for them, and Bob agreed.
The terms for each query are as follows:
ki, Bob pays for it.ki of it, and Alice pays the rest.Bob wants to select exactly mi chocolates such that his relative loss is minimized, more formally, if, in total, Alice has paid ai and Bob has paid bi, Bob wants to minimize bi - ai.
Return an integer array ans where ans[i] is Bob's minimum relative loss possible for queries[i].
Example 1:
Input: prices = [1,9,22,10,19], queries = [[18,4],[5,2]] Output: [34,-21] Explanation: For the 1st query Bob selects the chocolates with prices [1,9,10,22]. He pays 1 + 9 + 10 + 18 = 38 and Alice pays 0 + 0 + 0 + 4 = 4. So Bob's relative loss is 38 - 4 = 34. For the 2nd query Bob selects the chocolates with prices [19,22]. He pays 5 + 5 = 10 and Alice pays 14 + 17 = 31. So Bob's relative loss is 10 - 31 = -21. It can be shown that these are the minimum possible relative losses.
Example 2:
Input: prices = [1,5,4,3,7,11,9], queries = [[5,4],[5,7],[7,3],[4,5]] Output: [4,16,7,1] Explanation: For the 1st query Bob selects the chocolates with prices [1,3,9,11]. He pays 1 + 3 + 5 + 5 = 14 and Alice pays 0 + 0 + 4 + 6 = 10. So Bob's relative loss is 14 - 10 = 4. For the 2nd query Bob has to select all the chocolates. He pays 1 + 5 + 4 + 3 + 5 + 5 + 5 = 28 and Alice pays 0 + 0 + 0 + 0 + 2 + 6 + 4 = 12. So Bob's relative loss is 28 - 12 = 16. For the 3rd query Bob selects the chocolates with prices [1,3,11] and he pays 1 + 3 + 7 = 11 and Alice pays 0 + 0 + 4 = 4. So Bob's relative loss is 11 - 4 = 7. For the 4th query Bob selects the chocolates with prices [1,3,7,9,11] and he pays 1 + 3 + 4 + 4 + 4 = 16 and Alice pays 0 + 0 + 3 + 5 + 7 = 15. So Bob's relative loss is 16 - 15 = 1. It can be shown that these are the minimum possible relative losses.
Example 3:
Input: prices = [5,6,7], queries = [[10,1],[5,3],[3,3]] Output: [5,12,0] Explanation: For the 1st query Bob selects the chocolate with price 5 and he pays 5 and Alice pays 0. So Bob's relative loss is 5 - 0 = 5. For the 2nd query Bob has to select all the chocolates. He pays 5 + 5 + 5 = 15 and Alice pays 0 + 1 + 2 = 3. So Bob's relative loss is 15 - 3 = 12. For the 3rd query Bob has to select all the chocolates. He pays 3 + 3 + 3 = 9 and Alice pays 2 + 3 + 4 = 9. So Bob's relative loss is 9 - 9 = 0. It can be shown that these are the minimum possible relative losses.
Constraints:
1 <= prices.length == n <= 1051 <= prices[i] <= 1091 <= queries.length <= 105queries[i].length == 21 <= ki <= 1091 <= mi <= nProblem Overview: You are given chocolate prices and multiple queries. Each query asks for the minimum relative loss when buying exactly k chocolates while considering a threshold price m. The goal is to choose chocolates so the price difference relative to m is minimized while respecting the query constraints.
Approach 1: Brute Force Selection (O(n log n) per query time, O(1) space)
For every query, iterate through the entire price list and evaluate which k chocolates produce the smallest relative loss with respect to m. You can sort the prices or repeatedly select candidates near m, then compute the loss for the chosen set. This approach recomputes work for each query and may involve scanning the full array every time. With up to many queries, the repeated sorting or scanning becomes expensive.
Approach 2: Sorting + Binary Search + Prefix Sum (O((n + q) log n) time, O(n) space)
Sort the chocolate prices once. Precompute a prefix sum array so you can quickly calculate the total price of any contiguous segment. For each query, use binary search to find the boundary where prices become greater than m. This splits chocolates into two groups: prices ≤ m and prices > m. Since you must buy k chocolates, determine how many to take from each side to minimize the relative loss.
Prefix sums let you compute the sum of chosen chocolates in O(1), and binary search identifies candidate ranges in O(log n). The sorted order ensures you always consider the closest prices to the threshold first. This combination of sorting, binary search, and prefix sums removes repeated scanning and keeps each query efficient.
Recommended for interviews: The sorting + binary search + prefix sum solution is the expected approach. Brute force demonstrates understanding of the objective, but interviewers look for the ability to preprocess the array and answer multiple queries efficiently. Recognizing that the optimal choices lie around the threshold m and using prefix sums for fast range sums is the key insight.
Based on the problem description, we know:
If prices[i] leq k, then Bob needs to pay prices[i], and Alice doesn't need to pay. Therefore, Bob's relative loss is prices[i]. In this case, Bob should choose the chocolate with a lower price to minimize the relative loss.
If prices[i] > k, then Bob needs to pay k, and Alice needs to pay prices[i] - k. Therefore, Bob's relative loss is k - (prices[i] - k) = 2k - prices[i]. In this case, Bob should choose the chocolate with a higher price to minimize the relative loss.
Therefore, we first sort the price array prices, and then preprocess the prefix sum array s, where s[i] represents the sum of the prices of the first i chocolates.
Next, for each query [k, m], we first use binary search to find the index r of the first chocolate with a price greater than k. Then, we use binary search again to find the number of chocolates l that should be chosen on the left, so the number of chocolates that should be chosen on the right is m - l. At this point, Bob's relative loss is s[l] + 2k(m - l) - (s[n] - s[n - (m - l)]).
In the second binary search process mentioned above, we need to judge whether prices[mid] < 2k - prices[n - (m - mid)], where right represents the number of chocolates that should be chosen on the right. If this inequality holds, it means that choosing the chocolate at position mid has a lower relative loss, so we update l = mid + 1. Otherwise, it means that the chocolate at position mid has a higher relative loss, so we update r = mid.
The time complexity is O((n + m) times log n), and the space complexity is O(n). Where n and m are the lengths of the arrays prices and queries, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Selection | O(n log n) per query | O(1) | Small input sizes or when queries are very limited |
| Sorting + Binary Search + Prefix Sum | O((n + q) log n) | O(n) | Large arrays with many queries; optimal competitive programming and interview solution |
The unfair way I got good at Leetcode • Dave Burji • 596,394 views views
Watch 9 more video solutions →Practice Minimum Relative Loss After Buying Chocolates with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor