You are given two integer arrays costs and capacity, both of length n, where costs[i] represents the purchase cost of the ith machine and capacity[i] represents its performance capacity.
You are also given an integer budget.
You may select at most two distinct machines such that the total cost of the selected machines is strictly less than budget.
Return the maximum achievable total capacity of the selected machines.
Example 1:
Input: costs = [4,8,5,3], capacity = [1,5,2,7], budget = 8
Output: 8
Explanation:
costs[0] = 4 and costs[3] = 3.4 + 3 = 7, which is strictly less than budget = 8.capacity[0] + capacity[3] = 1 + 7 = 8.Example 2:
Input: costs = [3,5,7,4], capacity = [2,4,3,6], budget = 7
Output: 6
Explanation:
costs[3] = 4.budget = 7.capacity[3] = 6.Example 3:
Input: costs = [2,2,2], capacity = [3,5,4], budget = 5
Output: 9
Explanation:
costs[1] = 2 and costs[2] = 2.2 + 2 = 4, which is strictly less than budget = 5.capacity[1] + capacity[2] = 5 + 4 = 9.
Constraints:
1 <= n == costs.length == capacity.length <= 1051 <= costs[i], capacity[i] <= 1051 <= budget <= 2 * 105Problem Overview: You are given arrays describing capacity and cost, along with a total budget. The goal is to select valid elements such that the total cost stays within the budget while maximizing the achievable capacity. The challenge is balancing cost constraints with capacity maximization efficiently.
Approach 1: Brute Force Pair/Subset Check (O(n^2) time, O(1) space)
The most direct approach is to iterate through all valid combinations and compute their total cost and resulting capacity. For each candidate pair or combination, check whether the cost is within the budget and track the maximum capacity found. This uses simple Array iteration with nested loops. The approach is easy to implement but quickly becomes impractical as n grows because every pair (or candidate combination) must be evaluated.
Approach 2: Sorting + Two Pointers (O(n log n) time, O(1) space)
Sort the items by cost first. After sorting, use the two pointers technique to scan from both ends while maintaining the budget constraint. If the combined cost exceeds the budget, move the higher-cost pointer inward; otherwise compute the resulting capacity and update the answer. Sorting reduces the search space and allows efficient pruning during the scan. This technique is common in problems involving pair constraints and works well when decisions depend on ordered cost values. See more patterns in two pointers problems.
Approach 3: Sorting + Ordered Set (O(n log n) time, O(n) space)
Sort the elements by cost so that cheaper options are processed first. Maintain an ordered set (such as TreeSet, bisect-backed structure, or balanced BST) storing candidate capacities encountered so far. For each element, compute the remaining budget and use binary search on the ordered structure to find the best compatible candidate. This allows efficient lookup of the optimal capacity that fits within the remaining cost constraint. Each insertion and query takes O(log n), giving an overall O(n log n) solution. This approach combines sorting with binary search style lookups to avoid checking all pairs.
Recommended for interviews: Interviewers expect the optimized Sorting + Ordered Set or a similar O(n log n) strategy. Brute force demonstrates baseline reasoning but fails scalability constraints. Using sorting with efficient lookups shows you understand how to combine ordered data structures with binary search to prune the search space effectively.
We first filter out all machines with costs less than the budget and sort them by cost in ascending order, recording them in the array arr, where arr[i] = (costs[i], capacity[i]). If arr is empty, we cannot buy any machine, so we return 0.
Otherwise, we can obtain the machine with the maximum capacity in arr and initialize the answer with this capacity.
Next, we use a two-pointer approach to iterate through pairs of machines in arr, using an ordered set remain to maintain the capacities of all currently available machines. Initially, remain contains the capacities of all machines in arr.
We use pointers i and j pointing to the beginning and end of arr, respectively. For each i, we remove arr[i] from remain, and then move pointer j until arr[i].cost + arr[j].cost < budget. During this process, we remove the machines that do not satisfy the condition from remain. At this point, any machine in remain can be bought together with arr[i]. We take the machine with the maximum capacity from remain, add its capacity to arr[i]'s capacity, and update the answer. Finally, we return the answer.
The time complexity is O(n log n), and the space complexity is O(n), where n is the number of machines.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Small inputs or verifying correctness during prototyping |
| Sorting + Two Pointers | O(n log n) | O(1) | When evaluating pair combinations under a cost constraint |
| Sorting + Ordered Set | O(n log n) | O(n) | General scalable solution requiring fast lookups for best compatible candidate |
Maximum Capacity Within Budget 🔥 LeetCode 3814 | Weekly Contest 485 | Greedy + Sorting • Study Placement • 2,056 views views
Watch 6 more video solutions →Practice Maximum Capacity Within Budget with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor