Maximum Number of Items From Sale I - Video Solutions
LeetCode Weekly Contest 504 - Q2: Maximum Number of Items From Sale I | DP + Knapsack Intuition
Maximum Number of Items From Sale I - Video Solution
Watch 10 video solutions for Maximum Number of Items From Sale I, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by Madhumitha Kolkar has 928 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:
- For each item
ithat you bought at least one copy of, you receive one free copy of every itemjsuch thatj != iandfactoridividesfactorj. - Buying multiple copies of the same item
idoes not give additional free copies through itemi. - 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 = [[6,2],[2,6],[3,4]], budget = 9
Output: 4
Explanation:
- You can buy 2 copies of item 0 and 1 copy of item 2 for a total cost of
2 * 2 + 4 = 8, which is not greater thanbudget = 9. - Buying item 2 gives 1 free copy of item 0, because
factor2 = 3dividesfactor0 = 6. - You leave with 3 purchased copies and 1 free copy, for a total of 4 item copies.
Example 2:
Input: items = [[2,4],[3,2],[4,1],[6,4],[12,4]], budget = 8
Output: 10
Explanation:
- You can buy 1 copy of item 0, 1 copy of item 1, and 2 copies of item 2 for a total cost of
4 + 2 + 2 * 1 = 8. - Buying item 0 gives 1 free copy of items 2, 3, and 4.
- Buying item 1 gives 1 free copy of items 3 and 4.
- Buying item 2 gives 1 free copy of item 4.
- Thus, you receive 6 free copies. You leave with 4 purchased copies and 6 free copies, for a total of 10 item copies.
Constraints:
1 <= items.length <= 1000items[i] = [factori, pricei]1 <= factori, pricei <= 15001 <= budget <= 1500
Approach Overview
Problem Overview: You are given a list of item prices available during a sale and a limited budget. The goal is to buy the maximum number of items without exceeding the budget. Each item can be purchased at its available sale cost, so the strategy focuses on selecting items that allow the count to grow as large as possible.
Approach 1: Brute Force Subset Search (O(2^n) time, O(n) space)
The most direct way is to examine every possible subset of items. For each subset, compute the total price and track the largest subset whose sum does not exceed the budget. This approach uses recursion or bitmask enumeration to generate combinations. While it guarantees the optimal answer, the exponential time complexity makes it impractical even for moderate input sizes. It mainly serves as a conceptual baseline to understand the optimization goal.
Approach 2: Greedy with Sorting (O(n log n) time, O(1) extra space)
The key insight is that buying cheaper items first maximizes how many items you can afford. Sort the price array in ascending order. Then iterate from the smallest price and keep subtracting from the remaining budget until the next item cannot be afforded. Each successful purchase increments the item count. Sorting ensures that every unit of budget is used efficiently to maximize quantity instead of spending early on expensive items.
Approach 3: Prefix Sum Optimization (O(n log n) time, O(n) space)
After sorting the prices, build a prefix sum array where prefix[i] represents the total cost of the first i cheapest items. This allows quick checks of how many items can be bought within the budget. You can iterate through the prefix array or use binary search to find the largest index where the total cost is less than or equal to the budget. Prefix sums are especially useful when the problem extends to multiple budget queries or repeated checks.
These strategies rely on the same greedy principle commonly used in greedy algorithms. Sorting enables efficient selection and often pairs with techniques like two pointers or prefix sums for quick cumulative calculations.
Recommended for interviews: The greedy sorting approach is what interviewers typically expect. Start by explaining why brute force is infeasible due to exponential complexity, then derive the greedy insight that buying cheaper items first maximizes count. Implementing the sorted iteration solution in O(n log n) time clearly demonstrates algorithmic reasoning and practical efficiency.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n) | O(n) | Conceptual understanding or very small input sizes |
| Greedy Sorting | O(n log n) | O(1) | General case where you want the maximum item count within a budget |
| Prefix Sum After Sorting | O(n log n) | O(n) | Useful when multiple budget queries or fast cumulative checks are required |