What is the time complexity of LeetCode 2819. Minimum Relative Loss After Buying Chocolates?

The Python solution on this page runs in O((n + m) \times \log n).

What is the space complexity of LeetCode 2819. Minimum Relative Loss After Buying Chocolates?

The Python solution on this page uses O(n) auxiliary space.

Minimum Relative Loss After Buying Chocolates — LeetCode 2819 Python Solution

HardLeetCode PremiumArrayBinary SearchPrefix SumSorting

Problem: #2819
Pattern: Prefix Sum
Reading time: 5 min
Source: leetcode.com

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

Example

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.

Python solution

Python

class Solution:
    def minimumRelativeLosses(
        self, prices: List[int], queries: List[List[int]]
    ) -> List[int]:
        def f(k: int, m: int) -> int:
            l, r = 0, min(m, bisect_right(prices, k))
            while l < r:
                mid = (l + r) >> 1
                right = m - mid
                if prices[mid] < 2 * k - prices[n - right]:
                    l = mid + 1
                else:
                    r = mid
            return l

        prices.sort()
        s = list(accumulate(prices, initial=0))
        ans = []
        n = len(prices)
        for k, m in queries:
            l = f(k, m)
            r = m - l
            loss = s[l] + 2 * k * r - (s[n] - s[n - r])
            ans.append(loss)
        return ans

Complexity

Measure	Complexity
Time	O((n + m) \times \log n)
Space	O(n) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2819. Minimum Relative Loss After Buying Chocolates is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2819. Minimum Relative Loss After Buying Chocolates?: LeetCode 2819. Minimum Relative Loss After Buying Chocolates is rated Hard on LeetCode.
What is the time complexity of LeetCode 2819. Minimum Relative Loss After Buying Chocolates?: The Python solution on this page runs in O((n + m) \times \log n).
What is the space complexity of LeetCode 2819. Minimum Relative Loss After Buying Chocolates?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2819. Minimum Relative Loss After Buying Chocolates cover?: LeetCode 2819. Minimum Relative Loss After Buying Chocolates is tagged Array, Binary Search, Prefix Sum and Sorting on LeetCode.
Is LeetCode 2819. Minimum Relative Loss After Buying Chocolates a premium problem?: Yes. LeetCode 2819. Minimum Relative Loss After Buying Chocolates is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.