Minimum Relative Loss After Buying Chocolates
HardUpdated: Aug 2, 2025
Practice on:
Problem
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
kiof 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].
Examples
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 <= 10^51 <= prices[i] <= 10^91 <= queries.length <= 10^5queries[i].length == 21 <= ki <= 10^91 <= mi <= n
Solution
Method 1 – Sorting + Prefix Sums + Binary Search
Intuition
For each query, Bob wants to select mi chocolates to minimize his relative loss. Sort prices, use prefix sums, and for each query, select the mi lowest-loss chocolates (those with price ≤ ki first, then the rest).
Approach
- Sort prices, build prefix sums.
- For each query [ki, mi]:
- Use binary search to find count of chocolates with price ≤ ki.
- If mi ≤ count, Bob pays sum of mi lowest prices, Alice pays 0.
- Else, Bob pays sum of all ≤ ki, plus ki for each of the rest, Alice pays the rest.
Code
C++
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<long long> minimumRelativeLoss(std::vector<int>& prices, std::vector<std::vector<int>>& queries) {
int n = prices.size();
std::sort(prices.begin(), prices.end());
std::vector<long long> prefix(n+1,0);
for (int i = 0; i < n; ++i) prefix[i+1]=prefix[i]+prices[i];
std::vector<long long> ans;
for (auto& q : queries) {
int k=q[0], m=q[1];
int idx = std::upper_bound(prices.begin(), prices.end(), k)-prices.begin();
if (m <= idx) {
long long bob = prefix[m], alice = 0;
ans.push_back(bob-alice);
} else {
long long bob = prefix[idx]+(long long)(m-idx)*k;
long long alice = prefix[m]-prefix[idx];
ans.push_back(bob-alice);
}
}
return ans;
}
};
Go
import "sort"
func minimumRelativeLoss(prices []int, queries [][]int) []int64 {
n := len(prices)
sort.Ints(prices)
prefix := make([]int64, n+1)
for i := 0; i < n; i++ { prefix[i+1]=prefix[i]+int64(prices[i]) }
ans := make([]int64, len(queries))
for i, q := range queries {
k, m := q[0], q[1]
idx := sort.SearchInts(prices, k+1)
if m <= idx {
bob := prefix[m]; alice := int64(0)
ans[i]=bob-alice
} else {
bob := prefix[idx]+int64(m-idx)*int64(k)
alice := prefix[m]-prefix[idx]
ans[i]=bob-alice
}
}
return ans
}
Java
import java.util.*;
class Solution {
public long[] minimumRelativeLoss(int[] prices, int[][] queries) {
int n = prices.length;
Arrays.sort(prices);
long[] prefix = new long[n+1];
for (int i = 0; i < n; i++) prefix[i+1]=prefix[i]+prices[i];
long[] ans = new long[queries.length];
for (int i = 0; i < queries.length; i++) {
int k=queries[i][0], m=queries[i][1];
int idx = Arrays.binarySearch(prices, k+1);
if (idx < 0) idx = -idx-1;
if (m <= idx) {
long bob = prefix[m], alice = 0;
ans[i]=bob-alice;
} else {
long bob = prefix[idx]+(long)(m-idx)*k;
long alice = prefix[m]-prefix[idx];
ans[i]=bob-alice;
}
}
return ans;
}
}
Kotlin
class Solution {
fun minimumRelativeLoss(prices: IntArray, queries: Array<IntArray>): LongArray {
val n = prices.size
prices.sort()
val prefix = LongArray(n+1)
for (i in 0 until n) prefix[i+1]=prefix[i]+prices[i]
val ans = LongArray(queries.size)
for (i in queries.indices) {
val k=queries[i][0]; val m=queries[i][1]
var idx = prices.binarySearch(k+1)
if (idx < 0) idx = -idx-1
if (m <= idx) {
val bob = prefix[m]; val alice = 0L
ans[i]=bob-alice
} else {
val bob = prefix[idx]+(m-idx)*k.toLong()
val alice = prefix[m]-prefix[idx]
ans[i]=bob-alice
}
}
return ans
}
}
Python
from bisect import bisect_right
class Solution:
def minimumRelativeLoss(self, prices: list[int], queries: list[list[int]]) -> list[int]:
prices.sort()
prefix = [0]
for p in prices: prefix.append(prefix[-1]+p)
ans = []
for k,m in queries:
idx = bisect_right(prices, k)
if m <= idx:
bob = prefix[m]; alice = 0
ans.append(bob-alice)
else:
bob = prefix[idx]+(m-idx)*k
alice = prefix[m]-prefix[idx]
ans.append(bob-alice)
return ans
Rust
impl Solution {
pub fn minimum_relative_loss(mut prices: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> {
prices.sort();
let n = prices.len();
let mut prefix = vec![0i64; n+1];
for i in 0..n { prefix[i+1]=prefix[i]+prices[i] as i64; }
let mut ans = vec![];
for q in queries {
let k=q[0]; let m=q[1];
let idx = prices.binary_search(&(k+1)).unwrap_or_else(|x|x);
if m <= idx {
let bob = prefix[m]; let alice = 0;
ans.push(bob-alice);
} else {
let bob = prefix[idx]+(m-idx) as i64 * k as i64;
let alice = prefix[m]-prefix[idx];
ans.push(bob-alice);
}
}
ans
}
}
TypeScript
class Solution {
minimumRelativeLoss(prices: number[], queries: number[][]): number[] {
prices.sort((a,b)=>a-b);
const n = prices.length;
const prefix = [0];
for (let i = 0; i < n; i++) prefix.push(prefix[prefix.length-1]+prices[i]);
const ans = [];
for (const [k,m] of queries) {
let idx = prices.findIndex(x=>x>k);
if (idx === -1) idx = n;
if (m <= idx) {
const bob = prefix[m], alice = 0;
ans.push(bob-alice);
} else {
const bob = prefix[idx]+(m-idx)*k;
const alice = prefix[m]-prefix[idx];
ans.push(bob-alice);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n log n + q log n)— Sort prices, binary search for each query. - 🧺 Space complexity:
O(n)— For prefix sums.