Minimum Cost to Acquire Required Items solution and explanation
7 more videos on this problem
Minimum Cost to Acquire Required Items | LeetCode 3789 | Weekly Contest 482Sanyam IIT Guwahati · 12:27 · 678 views
Minimum Cost to Acquire Required Items 🔥 LeetCode 3789 | Greedy Cost Optimization | Contest Problem Study Placement · 8:06 · 203 views
Leetcode 3789. Minimum Cost to Acquire Required Items | Greedy | O(1) | Medium | C++Leet's Code · 22:32 · 74 views
3789. Minimum Cost to Acquire Required Items (Leetcode Medium)Programming Live with Larry · 7:20 · 70 views
LeetCode 3789 | Minimum Cost to Acquire Required Items | JavaCode Kage · 9:30 · 62 views
LeetCode Minimum Cost to Acquire Required ItemsR Sai Siddhu · 10:47 · 56 views
Leetcode || 3789. Minimum Cost to Acquire Required ItemsCodeTalk18 · 6:28 · 20 views
Weekly Contest 482 | 3789. Minimum Cost to Acquire Required Itemscoding-class · 6:43 · 17 views
The problem
You are given five integers cost1, cost2, costBoth, need1, and need2.
There are three types of items available:
- An item of type 1 costs
cost1and contributes 1 unit to the type 1 requirement only. - An item of type 2 costs
cost2and contributes 1 unit to the type 2 requirement only. - An item of type 3 costs
costBothand contributes 1 unit to both type 1 and type 2 requirements.
You must collect enough items so that the total contribution toward type 1 is at least need1 and the total contribution toward type 2 is at least need2.
Return an integer representing the minimum possible total cost to achieve these requirements.
Example 1:
Input: cost1 = 3, cost2 = 2, costBoth = 1, need1 = 3, need2 = 2
Output: 3
Explanation:
After buying three type 3 items, which cost 3 * 1 = 3, the total contribution to type 1 is 3 (>= need1 = 3) and to type 2 is 3 (>= need2 = 2).
Any other valid combination would cost more, so the minimum total cost is 3.
Example 2:
Input: cost1 = 5, cost2 = 4, costBoth = 15, need1 = 2, need2 = 3
Output: 22
Explanation:
We buy need1 = 2 items of type 1 and need2 = 3 items of type 2: 2 * 5 + 3 * 4 = 10 + 12 = 22.
Any other valid combination would cost more, so the minimum total cost is 22.
Example 3:
Input: cost1 = 5, cost2 = 4, costBoth = 15, need1 = 0, need2 = 0
Output: 0
Explanation:
Since no items are required (need1 = need2 = 0), we buy nothing and pay 0.
Constraints:
1 <= cost1, cost2, costBoth <= 1060 <= need1, need2 <= 109
Approach overview
Problem Overview: You must acquire a required number of items while minimizing the total cost. The challenge comes from multiple purchase options or pricing rules, where certain combinations or purchase sizes change the effective cost. The goal is to determine the cheapest strategy that still satisfies the required quantity.
Approach 1: Brute Force Enumeration (O(k) time, O(1) space)
The most direct way is to enumerate all reasonable purchase combinations and compute the total cost for each. For example, if there are bundle sizes or alternative purchase rules, iterate through how many times you apply each option and calculate the remaining items that must be bought individually. Each configuration produces a total cost, and you keep track of the minimum. This approach works because the number of realistic combinations is small and bounded. The downside is unnecessary repeated calculations when many combinations lead to the same effective purchase pattern.
This method is useful for validating logic during development or when constraints are tiny. It also helps reveal patterns that lead to a more optimized solution. The time complexity is O(k), where k represents the number of candidate purchase strategies you test, and space complexity remains O(1) since only a few counters and cost variables are stored.
Approach 2: Greedy Case Analysis (O(1) time, O(1) space)
A more efficient method relies on observing how the pricing rules interact. Instead of testing every possibility, analyze the structure of the pricing and derive a small number of meaningful cases. For example, compare the cost of buying items individually versus buying them in discounted groups. If a bundle provides a cheaper per‑item rate, maximize its usage; otherwise prefer individual purchases. In some scenarios you evaluate a few boundary cases such as "all bundles", "all individual", or "bundles plus remainder".
This turns the problem into a small mathematical comparison. You compute the total cost for each candidate case and return the minimum. Since the number of cases is constant, the algorithm runs in O(1) time and O(1) space. This pattern frequently appears in problems combining greedy decision making with small math calculations, where a local price advantage determines the optimal strategy.
Recommended for interviews: Greedy case analysis. Interviewers expect you to reason about the pricing structure and reduce the solution to a few deterministic scenarios instead of brute forcing every combination. Showing the brute force idea demonstrates understanding, but identifying the mathematical cases proves you can simplify the search space and derive an optimal O(1) solution.
Solution
We can divide the purchasing strategy into three cases:
- Only buy Type 1 and Type 2 items. The total cost is
a = need1 times cost1 + need2 times cost2. - Only buy Type 3 items. The total cost is
b = costBoth times max(need1, need2). - Buy some Type 3 items, and purchase Type 1 and Type 2 items separately for the remaining needs. Let
mn = min(need1, need2), then the total cost isc = costBoth times mn + (need1 - mn) times cost1 + (need2 - mn) times cost2.
Finally, we return the minimum value among the three cases, min(a, b, c).
The time complexity is O(1), and the space complexity is O(1).
class Solution:
def minimumCost(
self, cost1: int, cost2: int, costBoth: int, need1: int, need2: int
) -> int:
a = need1 * cost1 + need2 * cost2
b = costBoth * max(need1, need2)
mn = min(need1, need2)
c = costBoth * mn + (need1 - mn) * cost1 + (need2 - mn) * cost2
return min(a, b, c)class Solution {
public long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
long a = (long) need1 * cost1 + (long) need2 * cost2;
long b = (long) costBoth * Math.max(need1, need2);
int mn = Math.min(need1, need2);
long c = (long) costBoth * mn + (long) (need1 - mn) * cost1 + (long) (need2 - mn) * cost2;
return Math.min(a, Math.min(b, c));
}
}class Solution {
public:
long long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
long long a = 1LL * need1 * cost1 + 1LL * need2 * cost2;
long long b = 1LL * costBoth * max(need1, need2);
int mn = min(need1, need2);
long long c = 1LL * costBoth * mn
+ 1LL * (need1 - mn) * cost1
+ 1LL * (need2 - mn) * cost2;
return min({a, b, c});
}
};function minimumCost(
cost1: number,
cost2: number,
costBoth: number,
need1: number,
need2: number,
): number {
const a = need1 * cost1 + need2 * cost2;
const b = costBoth * Math.max(need1, need2);
const mn = Math.min(need1, need2);
const c = costBoth * mn + (need1 - mn) * cost1 + (need2 - mn) * cost2;
return Math.min(a, b, c);
}func minimumCost(cost1 int, cost2 int, costBoth int, need1 int, need2 int) int64 {
a := int64(need1)*int64(cost1) + int64(need2)*int64(cost2)
b := int64(costBoth) * int64(max(need1, need2))
mn := min(need1, need2)
c := int64(costBoth)*int64(mn) +
int64(need1-mn)*int64(cost1) +
int64(need2-mn)*int64(cost2)
return min(a, min(b, c))
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(k) | O(1) | When validating logic or when the number of possible purchase combinations is very small |
| Greedy Case Analysis | O(1) | O(1) | Preferred approach when pricing rules allow direct comparison between bundles and individual purchases |
Frequently asked questions
Is Minimum Cost to Acquire Required Items easy or hard?
This problem is generally considered Medium difficulty. The implementation itself is simple, but identifying the correct greedy cases and reducing the search space to a few mathematical comparisons requires careful reasoning.
Minimum Cost to Acquire Required Items Python/Java solution
The greedy solution translates directly into code in Python, Java, C++, Go, or TypeScript. Each implementation calculates the cost for the relevant purchase cases and returns the minimum value. Because the algorithm is O(1), the implementation is short and efficient in all languages.
How to solve Minimum Cost to Acquire Required Items in O(1)?
Identify the pricing structure and derive the meaningful purchase cases. Calculate the total cost for scenarios such as buying all items individually, maximizing discounted bundles, or combining bundles with remaining single items. Compare these constant cases and return the minimum cost.
What is the best approach for Minimum Cost to Acquire Required Items?
Greedy case analysis is the most efficient approach. Instead of checking every possible purchase combination, you analyze the pricing rules and evaluate a few key scenarios such as buying items individually, using discounted bundles, or mixing both. Since the number of cases is constant, the final algorithm runs in O(1) time and O(1) space.
Is Minimum Cost to Acquire Required Items asked at Google/Amazon/Meta?
Problems involving cost minimization with greedy reasoning appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem number may vary, the pattern of analyzing pricing rules and choosing the cheapest combination is common in coding interviews.
What data structure is used in Minimum Cost to Acquire Required Items?
The solution typically does not require complex data structures. It relies on simple variables and arithmetic comparisons, combined with greedy reasoning and mathematical case analysis.
What is the time complexity of Minimum Cost to Acquire Required Items?
The optimal greedy solution runs in O(1) time because it evaluates only a small fixed number of purchase scenarios. Space complexity is also O(1) since the algorithm stores only a few variables for counts and costs.