Maximum Number of Items From Sale I - Solution & Explanation

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.