Minimum Total Price After Applying Discounts solution and explanation
8 more videos on this problem
4014. Minimum Total Price After Applying Discounts (Leetcode Medium)Programming Live with Larry · 5:31 · 68 views
LeetCode 4014 Solution | Minimum Total Price After Applying Discounts | Easy Greedy ProblemLogic Mode · 10:36 · 44 views
LeetCode Weekly Contest 514 | 4014 & 4015 Explained in JavaProof2Code · 14:35 · 35 views
LeetCode 4014 — Minimum Total Price After Applying Discounts | Greedy ExplainedRitesh · 7:39 · 23 views
LeetCode: Minimum Total Price After Applying Discounts | C++ SolutionAeXel · 9:33 · 17 views
Leetcode Weekly 514 | Minimum Total Price After Applying Discounts.Aryan Raj · 14:48 · 12 views
Minimum Total Price After Applying DiscountsOwen Wu · 2:30 · 11 views
LeetCode 4014. Minimum Total Price After Applying Discounts | Weekly Contest 514 #leetcode #coding yoBro · 0:20 · 5 views
Weekly Contest 514 | Leetcode 4014 | Minimum Total Price After Applying DiscountsCode Like Him · 3:01 · 2 views
The problem
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] = 60toprices[1] = 30, thus30 * (100 - 60) / 100 = 12. - Apply
discounts[0] = 50toprices[2] = 21, thus21 * (100 - 50) / 100 = 10.5. prices[0] = 10receives 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] = 50toprices[0] = 100, thus100 * (100 - 50) / 100 = 50. - Apply
discounts[1] = 40toprices[1] = 70, thus70 * (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] = 100toprices[2] = 9, thus9 * (100 - 100) / 100 = 0. - Apply
discounts[1] = 100toprices[0] = 7, thus7 * (100 - 100) / 100 = 0. prices[1] = 3receives 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 <= 1051 <= prices[i] <= 1051 <= 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.
class Solution:
def minPrice(self, prices: list[int], discounts: list[int]) -> float:
prices.sort()
discounts.sort()
i, j = len(prices) - 1, len(discounts) - 1
ans = 0
while i >= 0 and j >= 0:
ans += prices[i] * (100 - discounts[j]) / 100
i -= 1
j -= 1
while i >= 0:
ans += prices[i]
i -= 1
return ansclass Solution {
public double minPrice(int[] prices, int[] discounts) {
Arrays.sort(prices);
Arrays.sort(discounts);
int i = prices.length - 1;
int j = discounts.length - 1;
double ans = 0;
while (i >= 0 && j >= 0) {
ans += prices[i] * (100 - discounts[j]) / 100.0;
i--;
j--;
}
while (i >= 0) {
ans += prices[i];
i--;
}
return ans;
}
}class Solution {
public:
double minPrice(vector<int>& prices, vector<int>& discounts) {
sort(prices.begin(), prices.end());
sort(discounts.begin(), discounts.end());
int i = prices.size() - 1;
int j = discounts.size() - 1;
double ans = 0;
while (i >= 0 && j >= 0) {
ans += prices[i] * (100 - discounts[j]) / 100.0;
i--;
j--;
}
while (i >= 0) {
ans += prices[i];
i--;
}
return ans;
}
};function minPrice(prices: number[], discounts: number[]): number {
prices.sort((a, b) => a - b);
discounts.sort((a, b) => a - b);
let i = prices.length - 1;
let j = discounts.length - 1;
let ans = 0;
while (i >= 0 && j >= 0) {
ans += (prices[i] * (100 - discounts[j])) / 100;
i--;
j--;
}
while (i >= 0) {
ans += prices[i];
i--;
}
return ans;
}func minPrice(prices []int, discounts []int) float64 {
sort.Ints(prices)
sort.Ints(discounts)
i := len(prices) - 1
j := len(discounts) - 1
var ans float64
for i >= 0 && j >= 0 {
ans += float64(prices[i]) * float64(100-discounts[j]) / 100.0
i--
j--
}
for i >= 0 {
ans += float64(prices[i])
i--
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Only for n ≤ 10 or conceptual understanding |
| Greedy + Sorting | O(n log n) | O(1) (or O(n) for sorting if not in-place) | General case, optimal for all inputs |
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.