Watch 7 video solutions for Maximum Capacity Within Budget, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by Study Placement has 2,056 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |