Skip to main content
Talentd

Maximum Capacity Within Budget - Solution & Explanation

MediumArrayTwo PointersBinary SearchSorting9 min readAsked at: Amazon, Microsoft
Practice this problem

Problem Statement

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:

  • Choose two machines with costs[0] = 4 and costs[3] = 3.
  • The total cost is 4 + 3 = 7, which is strictly less than budget = 8.
  • The maximum total capacity is 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:

  • Choose one machine with costs[3] = 4.
  • The total cost is 4, which is strictly less than budget = 7.
  • The maximum total capacity is capacity[3] = 6.

Example 3:

Input: costs = [2,2,2], capacity = [3,5,4], budget = 5

Output: 9

Explanation:

  • Choose two machines with costs[1] = 2 and costs[2] = 2.
  • The total cost is 2 + 2 = 4, which is strictly less than budget = 5.
  • The maximum total capacity is capacity[1] + capacity[2] = 5 + 4 = 9.

 

Constraints:

  • 1 <= n == costs.length == capacity.length <= 105
  • 1 <= costs[i], capacity[i] <= 105
  • 1 <= budget <= 2 * 105

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^2)O(1)Small inputs or verifying correctness during prototyping
Sorting + Two PointersO(n log n)O(1)When evaluating pair combinations under a cost constraint
Sorting + Ordered SetO(n log n)O(n)General scalable solution requiring fast lookups for best compatible candidate

Video Solution

Maximum Capacity Within Budget 🔥 LeetCode 3814 | Weekly Contest 485 | Greedy + Sorting • Study Placement • 2,196 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Maximum Capacity Within Budget easy or hard?
Maximum Capacity Within Budget is generally considered a Medium difficulty problem. The brute-force idea is straightforward, but reaching the optimal O(n log n) solution requires recognizing the need for sorting and binary-search-based lookups.
Maximum Capacity Within Budget Python/Java solution
Implement the optimized strategy by sorting items by cost and maintaining a sorted structure for candidate capacities. In Python, this can be done with a list and bisect operations or a library-backed sorted container. Java implementations often use TreeSet, while C++ commonly uses multiset.
How to solve Maximum Capacity Within Budget in O(n log n)?
Sort the elements by cost, then iterate through them while maintaining an ordered structure of candidate capacities. For each element, compute the remaining budget and perform a binary search to locate the best compatible candidate. This avoids checking every pair explicitly and keeps the total runtime at O(n log n).
What is the best approach for Maximum Capacity Within Budget?
The most practical approach uses sorting combined with an ordered set or balanced tree. After sorting by cost, you iterate through items and use binary search on previously processed candidates to find the best capacity that still fits within the remaining budget. This reduces the search from O(n^2) to O(n log n).
Is Maximum Capacity Within Budget asked at Google/Amazon/Meta?
Problems combining budget constraints, sorting, and binary search appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this problem test the ability to combine arrays, ordered data structures, and efficient lookups to reduce brute-force search.
What data structure is used in Maximum Capacity Within Budget?
The optimized approach typically uses an ordered set or balanced binary search tree. Structures like TreeSet (Java), multiset (C++), or a sorted list with binary search in Python allow efficient O(log n) insertions and lookups.
What is the time complexity of Maximum Capacity Within Budget?
The optimal solution runs in O(n log n) time due to sorting and ordered set operations. Each insertion and lookup in the ordered structure costs O(log n), and this happens once per element. Space complexity is typically O(n) for storing candidates.

Ready to solve this problem?

Practice Maximum Capacity Within Budget with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays