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

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5
6
7

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:

1
2
3
4
5
6

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^5
  • 1 <= prices[i] <= 10^9
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 1 <= ki <= 10^9
  • 1 <= 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

  1. Sort prices, build prefix sums.
  2. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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.