Watch 10 video solutions for Minimum Relative Loss After Buying Chocolates, a hard level problem involving Array, Binary Search, Sorting. This walkthrough by Dave Burji has 596,394 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |