Skip to main content
Talentd

Minimum Relative Loss After Buying Chocolates - Solution & Explanation

HardPremiumFree on FleetCodeArrayBinary SearchSortingPrefix Sum16 min read
Practice this problem

Problem Statement

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:

  • If the price of a chocolate is less than or equal to ki, Bob pays for it.
  • Otherwise, Bob pays 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 <= 105
  • 1 <= prices[i] <= 109
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 1 <= ki <= 109
  • 1 <= mi <= n

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SelectionO(n log n) per queryO(1)Small input sizes or when queries are very limited
Sorting + Binary Search + Prefix SumO((n + q) log n)O(n)Large arrays with many queries; optimal competitive programming and interview solution

Video Solution

The unfair way I got good at Leetcode • Dave Burji • 596,394 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Relative Loss After Buying Chocolates easy or hard?
Minimum Relative Loss After Buying Chocolates is rated Hard on LeetCode with an acceptance rate around 46%. The difficulty comes from combining multiple techniques—sorting, binary search boundaries, and prefix sums—to answer queries efficiently.
Minimum Relative Loss After Buying Chocolates Python/Java solution
Typical implementations sort the price list, build a prefix sum array, and answer each query using binary search. The same logic works across Python, Java, C++, Go, and TypeScript with O((n + q) log n) complexity.
What is the best approach for Minimum Relative Loss After Buying Chocolates?
The optimal solution uses sorting, binary search, and prefix sums. Sort the chocolate prices once, build a prefix sum array, and for each query use binary search to split prices around the threshold m. This allows fast computation of candidate groups and minimizes relative loss efficiently.
How to solve Minimum Relative Loss After Buying Chocolates in O((n+q) log n)?
First sort the price array and compute prefix sums. For each query, apply binary search to locate the split point where prices exceed m. Then evaluate how many chocolates to take from each side so that exactly k are selected while minimizing the relative loss using prefix-sum range calculations.
Is Minimum Relative Loss After Buying Chocolates asked at Google/Amazon/Meta?
Problems involving sorting, prefix sums, and binary search frequently appear in interviews at companies like Google, Amazon, and Meta. Variations that require optimizing selection around a threshold value are common in system and algorithm interviews.
What data structure is used in Minimum Relative Loss After Buying Chocolates?
The main structures are a sorted array of prices and a prefix sum array. Binary search is used to locate the position of the threshold m in the sorted list, enabling efficient range calculations.
What is the time complexity of Minimum Relative Loss After Buying Chocolates?
The optimal approach runs in O((n + q) log n) time. Sorting the prices takes O(n log n), and each query uses binary search in O(log n) with O(1) prefix-sum calculations. Space complexity is O(n) for the prefix sum array.

Ready to solve this problem?

Practice Minimum Relative Loss After Buying Chocolates with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays