Skip to main content
Talentd

Maximum Number of Items From Sale I - Solution & Explanation

MediumArrayDynamic ProgrammingGreedy10 min readAsked at: Microsoft
Practice this problem

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 i that you bought at least one copy of, you receive one free copy of every item j such that j != i and factori divides factorj.
  • Buying multiple copies of the same item i does not give additional free copies through item i.
  • The same item j can 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 than budget = 9.
  • Buying item 2 gives 1 free copy of item 0, because factor2 = 3 divides factor0 = 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 <= 1000
  • items[i] = [factori, pricei]
  • 1 <= factori, pricei <= 1500
  • 1 <= 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.

Solution

Since buying the first item of a type is special and yields free items, we consider the first purchased item separately from the later purchases.

For the first purchased item, suppose we spend a budget of i and obtain f[i] items in total, including both the purchased item and the free items. For the later purchases, we can use the remaining budget budget - i to buy the cheapest item, obtaining \lfloor \frac{budget - i}{mn} \rfloor items, where mn is the minimum price among all items. Therefore, we enumerate the budget i spent on the first purchase and compute the maximum value of f[i] + \lfloor \frac{budget - i}{mn} \rfloor, which is the final answer.

The time complexity is O(n^2 + n times m), where n is the number of items and m is the budget.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subset EnumerationO(2^n)O(n)Conceptual understanding or very small input sizes
Greedy SortingO(n log n)O(1)General case where you want the maximum item count within a budget
Prefix Sum After SortingO(n log n)O(n)Useful when multiple budget queries or fast cumulative checks are required

Video Solution

LeetCode Weekly Contest 504 - Q2: Maximum Number of Items From Sale I | DP + Knapsack Intuition • Madhumitha Kolkar • 928 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Number of Items From Sale I easy or hard?
The problem is rated Medium because the greedy insight must be recognized quickly. Once you realize that buying cheaper items first maximizes the count, the implementation becomes straightforward. Most of the complexity lies in identifying the correct strategy rather than coding difficulty.
Maximum Number of Items From Sale I Python/Java solution
The typical implementation sorts the price array and iterates through it while subtracting each price from the remaining budget. Increment a counter for every successful purchase. The same logic translates directly across Python, Java, and C++ because it relies only on sorting and simple iteration.
How to solve Maximum Number of Items From Sale I in O(n)?
A strict O(n) solution is generally not possible unless the price range is limited enough to allow counting sort or bucket techniques. In the standard scenario, sorting the prices is required to guarantee optimal item selection. That leads to an O(n log n) greedy solution followed by a linear pass.
What is the best approach for Maximum Number of Items From Sale I?
The greedy sorting approach works best. Sort all item prices in ascending order and purchase items from cheapest to most expensive until the budget runs out. This guarantees the maximum number of items because cheaper purchases preserve more remaining budget. The algorithm runs in O(n log n) time due to sorting.
Is Maximum Number of Items From Sale I asked at Google/Amazon/Meta?
Problems based on greedy selection and budget constraints frequently appear in interviews at large tech companies such as Amazon and Google. Variants include maximizing purchases, minimizing cost, or selecting tasks within constraints. The underlying pattern—sort by cost and consume budget greedily—is a common interview theme.
What data structure is used in Maximum Number of Items From Sale I?
The core data structure is an array or list of prices. The algorithm primarily relies on sorting the array and then iterating through it while tracking the remaining budget. Some implementations also use prefix sums to quickly evaluate cumulative costs.
What is the time complexity of Maximum Number of Items From Sale I?
The optimal solution runs in O(n log n) time because the prices must be sorted before selecting items. After sorting, a single linear scan determines how many items can be purchased within the budget. The additional space complexity is O(1) if sorting is done in place.

Ready to solve this problem?

Practice Maximum Number of Items From Sale I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays