Maximum Number of Items From Sale II - Video Solutions
Maximum Number of Items From Sale II | Leetcode 3947
Maximum Number of Items From Sale II - Video Solution
Watch 6 video solutions for Maximum Number of Items From Sale II, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Techdose has 735 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a 2D integer array items, where items[i] = [factori, pricei] represents the ith item. You are also given an integer budget.
There are unlimited copies of each item available for purchase. You may buy any number of copies of any items such that the total cost of the purchased copies is at most budget.
After buying items, you may receive free copies according to the following rules:
- Each purchased copy of item
ican give you at most one free copy of another itemj. - The free item must satisfy
i != jandfactoridividesfactorj. - For each ordered pair
(i, j), you can receive a free copy of itemjfrom purchases of itemiat most once, regardless of how many copies of itemiyou buy. - The same item
jcan be received multiple times for free if it is received from purchases of different item types.
Return the maximum total number of item copies you can obtain, including both purchased copies and free copies, while spending at most budget on purchased items.
Example 1:
Input: items = [[1,6],[2,4],[3,5]], budget = 19
Output: 5
Explanation:
- You can buy 2 copies of item 0 and 1 copy of item 1 for a total cost of
2 * 6 + 4 = 16, which is not greater thanbudget = 19. - One purchased copy of item 0 gives 1 free copy of item 1, because
factor0 = 1dividesfactor1 = 2. - The other purchased copy of item 0 gives 1 free copy of item 2, because
factor0 = 1dividesfactor2 = 3. - You leave with 3 purchased copies and 2 free copies, for a total of 5 item copies.
Example 2:
Input: items = [[2,8],[1,10],[6,6],[4,12],[5,20],[5,17]], budget = 35
Output: 7
Explanation:
- You can buy 2 copies of item 0, 1 copy of item 1, and 1 copy of item 2 for a total cost of
2 * 8 + 10 + 6 = 32, which is not greater thanbudget = 35. - One purchased copy of item 0 gives 1 free copy of item 2, because
factor0 = 2dividesfactor2 = 6. - The other purchased copy of item 0 gives 1 free copy of item 3, because
factor0 = 2dividesfactor3 = 4. - The purchased copy of item 1 gives 1 free copy of item 2, because
factor1 = 1dividesfactor2 = 6. - Buying item 2 gives no free copy, because
factor2 = 6does not divide the factor of any other item. - You leave with 4 purchased copies and 3 free copies, for a total of 7 item copies.
Constraints:
1 <= items.length <= 105items[i] = [factori, pricei]1 <= factori <= items.length1 <= pricei <= 1091 <= budget <= 109
Approach Overview
Problem Overview: You are given item prices, a limited number of coins, and a fixed number of discount coupons. Each coupon can reduce the price of one item (for example, half price). The goal is to maximize how many items you can buy without exceeding the coin budget.
Approach 1: Brute Force Subset Search (Exponential Time)
Enumerate every subset of items and simulate applying coupons in the most beneficial way for that subset. For each chosen group, assign coupons to the most expensive items and check whether the total cost stays within the coin limit. This guarantees the optimal result but requires checking 2^n subsets, giving O(2^n * n log n) time and O(n) space. It quickly becomes infeasible even for moderate input sizes.
Approach 2: Greedy with Sorting (O(n log n) time, O(1) space)
Sort items by price and buy the cheapest items first. This greedy idea works well when coupons are not involved because minimizing cost lets you purchase more items. After sorting, iterate through the prices and subtract from the coin budget until the budget runs out. While simple, this strategy fails when coupons should be applied to expensive items later in the purchase sequence.
Approach 3: Greedy + Max Heap for Coupon Optimization (O(n log n) time, O(n) space)
Sort items by price and iterate through them while simulating purchases. Maintain a running total cost and a max heap storing the prices of items bought so far. When coupons are available, you can retroactively apply a coupon to the most expensive purchased item to reduce the total cost. This works because applying discounts to larger prices yields the biggest savings. Each time the cost exceeds the coin budget, use a coupon on the highest price from the heap (if any remain) and adjust the total. The heap ensures the optimal coupon placement with O(log n) updates.
This pattern appears in problems combining greedy decision making with dynamic re‑evaluation using a priority queue. Sorting establishes purchase order, while the heap allows you to reassign discounts to maximize savings.
Recommended for interviews: The greedy + heap approach is the expected solution. Brute force demonstrates understanding but is not scalable. Interviewers typically want to see the insight that coupons should always be applied to the most expensive purchased item, implemented efficiently using a priority queue.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Search | O(2^n * n log n) | O(n) | Only for conceptual understanding or very small inputs |
| Greedy After Sorting | O(n log n) | O(1) | Works when coupons or dynamic discounts are not involved |
| Greedy + Max Heap | O(n log n) | O(n) | General case with coupons or adjustable discounts |