Skip to main content
Talentd

Minimum Total Price After Applying Discounts - Solution & Explanation

MediumArrayTwo PointersGreedySorting9 min read
Practice this problem

Problem Statement

You are given two integer arrays prices and discounts.

The value prices[i] represents the price of the ith item, and discounts[j] represents a discount percentage.

You may apply discounts subject to the following rules:

  • Each discount can be applied to at most one item.
  • Each item can receive at most one discount.
  • An item may also receive no discount.

If a discount of d percent is applied to an item with price p, its final price becomes (p * (100 - d)) / 100. The final price is not rounded.

Return the minimum possible sum of final prices after assigning discounts optimally. Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

Input: prices = [10,30,21], discounts = [50,60]

Output: 32.50000

Explanation:

  • Apply discounts[1] = 60 to prices[1] = 30, thus 30 * (100 - 60) / 100 = 12.
  • Apply discounts[0] = 50 to prices[2] = 21, thus 21 * (100 - 50) / 100 = 10.5.
  • prices[0] = 10 receives no discount, so it stays 10.

The total is 12 + 10.5 + 10 = 32.50000, which is the minimum possible.

Example 2:

Input: prices = [100,70], discounts = [10,40,50]

Output: 92.00000

Explanation:​​​​​​​

  • Apply discounts[2] = 50 to prices[0] = 100, thus 100 * (100 - 50) / 100 = 50.
  • Apply discounts[1] = 40 to prices[1] = 70, thus 70 * (100 - 40) / 100 = 42.

The total is 50 + 42 = 92.00000, which is the minimum possible.

Example 3:

Input: prices = [7,3,9], discounts = [100,100]

Output: 3.00000

Explanation:

  • Apply discounts[0] = 100 to prices[2] = 9, thus 9 * (100 - 100) / 100 = 0.
  • Apply discounts[1] = 100 to prices[0] = 7, thus 7 * (100 - 100) / 100 = 0.
  • prices[1] = 3 receives no discount, so it stays 3.

The total is 0 + 0 + 3 = 3.00000, which is the minimum possible.

 

Constraints:

  • 1 <= prices.length, discounts.length <= 105
  • 1 <= prices[i] <= 105
  • 1 <= discounts[j] <= 100

Approach Overview

Problem Overview: You are given a list of items with prices and corresponding discount percentages. Applying a discount to an item reduces its price by that percentage. You must choose exactly one discount per item to minimize the total price. The catch is that you can apply each discount to only one item, so the assignment matters.

Approach 1: Brute Force (O(2^n) Time, O(n) Space)

Try all possible assignments of discounts to items. For each permutation, compute the total discounted price and track the minimum. This works for tiny inputs but explodes exponentially. You'd generate all n! permutations (or subsets if discounts are reusable? Actually if each discount can be used once, it's a permutation). For n=12, 12! is huge. This approach shows you understand the problem but is impractical.

Approach 2: Greedy + Sorting (O(n log n) Time, O(1) Space)

Sort items by their discount amount (price * discount%) in descending order. Assign the largest discounts to the most expensive items. This works because the total saving is maximized when you apply the highest percentage to the highest price. Mathematically, the total price after discounts is minimized by maximizing sum(price_i * discount_i), which is maximized by sorting both in the same order (rearrangement inequality). You sort items by price and discounts by discount% in descending order, then pair them. This gives the optimal total price.

Recommended for interviews: Interviewers expect the greedy sorting solution. Brute force shows you can model the problem, but the greedy approach demonstrates you can spot the rearrangement inequality and apply it. The optimal solution is O(n log n) due to sorting, and it's the most efficient possible since any solution must at least look at all items.

Related topics: Greedy Algorithms, Sorting, Arrays.

Solution

To minimize the total price, we need to maximize the total amount saved by discounts. Applying a discount d to an item with price p saves p times d / 100. By the rearrangement inequality, applying larger discounts to more expensive items maximizes the total savings.

Therefore, we sort both prices and discounts in ascending order, then use two pointers starting from the ends of both arrays, repeatedly applying the current largest discount to the current most expensive item and accumulating the discounted price. Once all discounts are used up, the remaining items are added at their original prices.

The time complexity is O(n times log n + m times log m), and the space complexity is O(log n + log m). Here, n and m are the lengths of the arrays prices and discounts, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(2^n)O(n)Only for n ≤ 10 or conceptual understanding
Greedy + SortingO(n log n)O(1) (or O(n) for sorting if not in-place)General case, optimal for all inputs

Video Solution

4014. Minimum Total Price After Applying Discounts (Leetcode Medium) • Programming Live with Larry • 68 views views

Watch 8 more video solutions →

Frequently Asked Questions

Minimum Total Price After Applying Discounts Python solution
In Python, sort both arrays in descending order using sorted() with reverse=True, then zip them and sum the discounted prices. Code: sum(price * (1 - discount/100) for price, discount in zip(sorted(prices, reverse=True), sorted(discounts, reverse=True))). That's it.
Is Minimum Total Price After Applying Discounts easy or hard?
The problem is rated Medium. The naive brute-force approach is exponential, but the greedy sorting solution is straightforward once you see the rearrangement inequality. Most candidates solve it with sorting in O(n log n) after a bit of thought.
How to solve Minimum Total Price After Applying Discounts in O(n log n)?
Sort the item prices in descending order and sort the discount percentages in descending order. Then pair item i with discount i and sum the discounted prices. This maximizes savings because larger discounts are applied to higher-priced items, proven by the rearrangement inequality.
What is the best approach for Minimum Total Price After Applying Discounts?
The best approach is greedy with sorting. Sort items by price descending and discounts by percentage descending, then pair the largest discount with the most expensive item. This runs in O(n log n) time and O(1) space, achieving the minimum possible total price.
Is Minimum Total Price After Applying Discounts asked at Google/Meta/Amazon?
Yes, this problem tests greedy thinking and sorting, common in interviews at top tech companies. It's a variation of assignment problems that appear in coding rounds at Google, Meta, and Amazon, usually as a medium-difficulty question.
What data structure is used in Minimum Total Price After Applying Discounts?
The solution uses arrays or lists to store prices and discounts candidate, then sorts them. No complex data structures are needed—just sorting and a loop to compute the sum. The key is recognizing the greedy pattern.
What is the time complexity of Minimum Total Price After Applying Discounts?
The optimal solution uses sorting, so time complexity is O(n log n). Space complexity is O(1) if sorting in-place (or O(n) if using extra arrays). This is the best you can do because you must inspect every item and discount.

Ready to solve this problem?

Practice Minimum Total Price After Applying Discounts with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays