Maximum Number of Items From Sale II - Solution & Explanation

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.