Leetcode Problem 2819. Minimum Relative Loss After Buying Chocolates

2819. Minimum Relative Loss After Buying Chocolates

Leetcode Solutions

Sorting, Prefix Sums, and Binary Search

  1. Sort the prices array in ascending order.
  2. Compute the prefix sums of the sorted prices array.
  3. For each query [ki, mi], perform the following steps: a. Find the number of chocolates with a price less than or equal to ki using binary search. b. Initialize two pointers to find the optimal split between cheaper and more expensive chocolates. c. Use binary search to find the maximum number of expensive chocolates Bob can pay for such that his relative loss is minimized. d. Calculate Bob's total payment and Alice's total payment based on the split. e. Compute Bob's relative loss as the difference between his payment and Alice's payment.
  4. Return the array of minimum relative losses for each query.
UML Thumbnail

Brute Force with Sorting

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...