LeetCode Problem 2819

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Sorting, Prefix Sum

Solution

LeetCode 2819 - Minimum Relative Loss After Buying Chocolates

Problem Understanding

We are given an array prices, where each value represents the price of a chocolate. For every query [k, m], Bob wants to choose exactly m chocolates.

The payment rule depends on the threshold k:

• If a chocolate costs at most k, Bob pays the entire price.
• If a chocolate costs more than k, Bob pays exactly k, and Alice pays the remaining amount.

Suppose Bob chooses a set of chocolates. Let:

• b = total amount paid by Bob
• a = total amount paid by Alice

Bob's relative loss is defined as:

$$b - a$$

For each query, we must find the minimum possible value of b - a among all ways to choose exactly m chocolates.

The array length and the number of queries are both up to 10^5, so any solution that examines all subsets or even all possible groups of size m is completely infeasible. We need an algorithm that can answer each query in roughly logarithmic time after preprocessing.

A few observations are immediately important.

For a chocolate with price p:

• If p ≤ k, then Bob pays p and Alice pays 0, contributing

$$p$$

to b - a.

• If p > k, then Bob pays k and Alice pays p-k, contributing

$$k-(p-k)=2k-p$$

to b-a.

Therefore every chocolate independently contributes:

$$f(p)= \begin{cases} p,& p\le k\ 2k-p,& p>k \end{cases}$$

For a fixed query, the problem becomes:

Choose exactly m chocolates whose contribution values sum to the minimum possible total.

This reformulation is the key to the entire solution.

Important edge cases include:

• k smaller than every chocolate price.
• k larger than every chocolate price.
• m = 1.
• m = n.
• Multiple equal prices.
• Prices as large as 10^9, requiring 64-bit arithmetic.

The problem guarantees:

• 1 ≤ n ≤ 10^5
• 1 ≤ q ≤ 10^5
• All prices are positive.
• Every query requests a valid number of chocolates.

Approaches

Brute Force

For a fixed query, we can compute the contribution of every chocolate and then choose the smallest m contributions.

This is correct because the objective is simply the sum of chosen contribution values.

However, doing this independently for every query requires:

1. Computing n contributions.
2. Sorting them.
3. Summing the smallest m.

That costs O(n log n) per query.

With both n and q up to 10^5, this becomes far too slow.

Key Insight

After sorting the prices, the contribution function has a very special structure.

For a query threshold k:

$$f(p)=p \quad (p\le k)$$

and

$$f(p)=2k-p \quad (p>k)$$

Notice:

• For prices ≤ k, contributions increase with price.
• For prices > k, contributions decrease with price.

Therefore:

• Among chocolates priced above k, the cheapest contributions come from the largest prices.
• Among chocolates priced at most k, the cheapest contributions come from the smallest prices.

After sorting the prices:

• The left side (≤ k) contributes candidates from the beginning.
• The right side (> k) contributes candidates from the end.

The optimal set of m chocolates must therefore consist of:

• some number x taken from the left prefix,
• and m-x taken from the right suffix.

No middle elements are ever needed.

This reduces the problem to finding the correct value of x.

Even better, we can derive a monotonic condition and use binary search.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q · n log n)	O(n)	Recompute contributions for every query
Optimal	O(n log n + q log n)	O(n)	Sort once, answer each query with binary search

Algorithm Walkthrough

Assume the prices are sorted.

Let:

• pos = upper_bound(prices, k)
• cnt = pos

Then:

• indices [0, cnt-1] contain prices ≤ k
• indices [cnt, n-1] contain prices > k

Let x be the number chosen from the left part.

Then:

• m-x are chosen from the right part.

Step 1

Sort the prices and build prefix sums.

Let:

$$prefix[i]$$

store the sum of the first i sorted prices.

This allows constant-time range-sum queries.

Step 2

For a query (k,m), find

$$cnt = #{p \le k}$$

using binary search.

Step 3

Observe the optimal candidates.

If we choose x chocolates from the left side, the minimum contribution from that side comes from the smallest x prices.

Their contribution sum is:

$$L(x)=prefix[x]$$

If we choose m-x chocolates from the right side, the minimum contribution comes from the largest m-x prices.

Let

$$S$$

be the sum of those largest prices.

Their contribution becomes:

$$(m-x)\cdot 2k - S$$

Step 4

Determine the valid range of x.

We cannot choose more than cnt chocolates from the left side.

We also cannot choose more than n-cnt chocolates from the right side.

Therefore:

$$\max(0,m-(n-cnt)) \le x \le \min(m,cnt)$$

Step 5

Derive the optimal boundary.

Increasing x by one means:

• removing one chosen right-side chocolate,
• adding one left-side chocolate.

The objective changes monotonically.

After algebra, the optimal x becomes the largest valid value satisfying:

$$prices[x-1]+prices[n-(m-x)] \le 2k$$

This condition is monotonic in x, so binary search can find the best value.

Step 6

Compute the answer for that optimal x.

The left contribution is:

$$prefix[x]$$

The right contribution uses the largest m-x prices:

$$S = prefix[n]-prefix[n-(m-x)]$$

Thus:

$$answer = prefix[x] + (m-x)\cdot 2k - S$$

Why it Works

The contribution values form two monotonic groups:

• increasing among prices ≤ k,
• decreasing among prices > k.

Therefore the globally smallest contribution values must come from the smallest prices on the left and the largest prices on the right.

The choice is completely determined by how many items are taken from each side. The marginal effect of increasing x is monotonic, producing a binary-searchable boundary. Once the optimal x is found, the corresponding contribution sum is exactly the minimum relative loss.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:
        prices.sort()
        n = len(prices)

        prefix = [0] * (n + 1)
        for i, p in enumerate(prices):
            prefix[i + 1] = prefix[i] + p

        answers = []

        for k, m in queries:
            cnt = bisect_right(prices, k)

            low = max(0, m - (n - cnt))
            high = min(m, cnt)

            l, r = low, high
            while l < r:
                mid = (l + r + 1) // 2

                left_price = prices[mid - 1]
                right_price = prices[n - (m - mid)]

                if left_price + right_price <= 2 * k:
                    l = mid
                else:
                    r = mid - 1

            x = l

            left_sum = prefix[x]

            take_right = m - x
            right_sum = prefix[n] - prefix[n - take_right]

            answer = left_sum + take_right * (2 * k) - right_sum
            answers.append(answer)

        return answers

Implementation Explanation

The first step sorts the prices and constructs a prefix-sum array. The prefix sums allow us to obtain the sum of any prefix or suffix in constant time.

For each query, bisect_right finds how many prices are at most k. This divides the sorted array into the two regions required by the contribution function.

The variable x represents how many chocolates are chosen from the left region. The feasible interval for x is computed from the available counts on both sides.

A binary search then finds the largest valid x satisfying the optimality condition

$$prices[x-1] + prices[n-(m-x)] \le 2k.$$

Once x is known, the selected left chocolates are exactly the first x prices, and the selected right chocolates are exactly the largest m-x prices. Prefix sums provide both totals immediately.

The final formula directly computes Bob's minimum relative loss.

Go Solution

package main

import "sort"

func minimumRelativeLosses(prices []int, queries [][]int) []int64 {
	sort.Ints(prices)

	n := len(prices)

	prefix := make([]int64, n+1)
	for i, p := range prices {
		prefix[i+1] = prefix[i] + int64(p)
	}

	ans := make([]int64, len(queries))

	for qi, q := range queries {
		k := q[0]
		m := q[1]

		cnt := sort.Search(n, func(i int) bool {
			return prices[i] > k
		})

		low := max(0, m-(n-cnt))
		high := min(m, cnt)

		l, r := low, high
		for l < r {
			mid := (l + r + 1) / 2

			leftPrice := prices[mid-1]
			rightPrice := prices[n-(m-mid)]

			if leftPrice+rightPrice <= 2*k {
				l = mid
			} else {
				r = mid - 1
			}
		}

		x := l

		leftSum := prefix[x]

		rightCount := m - x
		rightSum := prefix[n] - prefix[n-rightCount]

		ans[qi] = leftSum + int64(rightCount)*int64(2*k) - rightSum
	}

	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Go-Specific Notes

The logic is identical to the Python solution. The main difference is that all arithmetic involving sums uses int64, because the total price of selected chocolates can exceed the range of a 32-bit integer.

Go's sort.Search is used both for finding the partition point and for implementing binary search efficiently.

Worked Examples

Example 1

Input:

prices = [1,9,22,10,19]
query = [18,4]

Sorted prices:

[1,9,10,19,22]

Prefix sums:

i	prefix[i]
0	0
1	1
2	10
3	20
4	39
5	61

cnt = 3 because [1,9,10] ≤ 18.

Valid range:

low=max(0,4-2)=2
high=min(4,3)=3

Binary search:

x	Condition
3	10 + 19 = 29 ≤ 36

Optimal:

x = 3

Compute:

left_sum = 20
take_right = 1
right_sum = 22

Answer:

20 + 36 - 22 = 34

Example 2, Query [5,4]

Sorted:

[1,3,4,5,7,9,11]

cnt = 4

Valid range:

1 ≤ x ≤ 4

Binary search yields:

x = 2

Compute:

left_sum = 1 + 3 = 4
right_sum = 7 + 9 + 11 = 27

Answer:

4 + 3*10 - 27
= 4

Example 2, Query [5,7]

All chocolates must be selected.

x = 4

Compute:

left_sum = 13
right_sum = 27

Answer:

13 + 3*10 - 27 = 16

Example 3

Input:

prices = [5,6,7]
query = [3,3]

All prices exceed k.

cnt = 0
x = 0

Right sum:

5 + 6 + 7 = 18

Answer:

3*6 - 18 = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + q log n)	Sort once, binary search per query
Space	O(n)	Prefix-sum array

The dominant preprocessing cost is sorting the prices. After that, each query performs two binary searches and constant-time prefix-sum calculations, resulting in O(log n) per query. With up to 10^5 queries, this comfortably fits within the constraints.

Test Cases

sol = Solution()

assert sol.minimumRelativeLosses(
    [1,9,22,10,19],
    [[18,4],[5,2]]
) == [34, -21]  # example 1

assert sol.minimumRelativeLosses(
    [1,5,4,3,7,11,9],
    [[5,4],[5,7],[7,3],[4,5]]
) == [4, 16, 7, 1]  # example 2

assert sol.minimumRelativeLosses(
    [5,6,7],
    [[10,1],[5,3],[3,3]]
) == [5, 12, 0]  # example 3

assert sol.minimumRelativeLosses(
    [10],
    [[5,1]]
) == [0]  # single chocolate above k

assert sol.minimumRelativeLosses(
    [3],
    [[10,1]]
) == [3]  # single chocolate below k

assert sol.minimumRelativeLosses(
    [5,5,5,5],
    [[5,2]]
) == [10]  # duplicate values

assert sol.minimumRelativeLosses(
    [1,2,3,4,5],
    [[100,3]]
) == [6]  # all prices <= k

assert sol.minimumRelativeLosses(
    [1,2,3,4,5],
    [[1,5]]
) == [-3]  # all chocolates selected

assert sol.minimumRelativeLosses(
    [10**9,10**9,10**9],
    [[10**9,3]]
) == [3000000000]  # large values

Test Summary

Test	Why
Example 1	Verifies mixed selection from both sides
Example 2	Verifies multiple query types
Example 3	Verifies all prices greater than k
Single chocolate above k	Smallest possible input
Single chocolate below k	Boundary case
Duplicate prices	Ensures equal values work correctly
All prices ≤ k	Entire array on left side
All chocolates selected	Tests m = n
Large values	Verifies 64-bit arithmetic

Edge Cases

All Prices Are Greater Than k

When every chocolate price exceeds k, we have cnt = 0. No chocolates can be chosen from the left side, so x = 0 is forced. The algorithm naturally handles this because the valid range collapses to a single value. The answer becomes the contribution sum of the largest m prices under the formula 2k-p.

All Prices Are Less Than or Equal to k

In this situation, every contribution equals the original price. The optimal strategy is simply selecting the m smallest prices. Since cnt = n, the binary search ultimately chooses the maximum feasible x, causing the formula to reduce exactly to the sum of the smallest m prices.

Selecting Every Chocolate

When m = n, there is no choice of subset. A common source of bugs is incorrect suffix indexing because the number of right-side selections becomes completely determined by the partition. The implementation carefully computes the valid interval for x, ensuring all indices remain valid and the final formula still works.

Large Price Values

Prices can reach 10^9, and up to 10^5 chocolates may be selected. The resulting sums can be around 10^14. Using 32-bit integers would overflow. The Python implementation is naturally safe because Python integers are arbitrary precision, while the Go implementation explicitly uses int64 for all prefix sums and answer calculations.