3814. Maximum Capacity Within Budget

MediumArrayTwo PointersBinary SearchSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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.

In other words, you can choose either:

One machine whose cost is strictly less than budget, or
Two distinct machines whose combined cost is strictly less than budget.

Among all valid choices, you want to maximize the sum of the selected machines' capacities. If it is possible to pick two machines, their capacities are added together; if only one machine fits within the budget, only its capacity counts. When no machine can be purchased within the budget, the answer is 0.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Two pointers?

This problem maps to Two pointers through a short path in the full flowchart.

Sorting machines by cost and using two pointers to find the best pair within budget exploits the monotonic narrowing of valid partner candidates.

Open in Flowchart

Intuition

The key observation is that we are choosing at most two machines, so we essentially have two scenarios to handle: picking a single machine, or picking a pair of machines.

For the single machine case, we simply need to find the machine with the largest capacity whose cost is strictly less than budget. This is straightforward.

For the two machine case, the difficulty is that we want to maximize the total capacity while keeping the total cost under budget. A naive approach would check every pair, taking O(n^2) time. We can do better by noticing a useful monotonic relationship.

If we sort the machines by cost in ascending order, then for a fixed machine at position i, as we look at candidates from the right end of the sorted array, the larger the cost of the partner machine, the more likely it violates the budget. So if we fix the cheaper machine arr[i], there is a threshold cost beyond which no partner is allowed. Specifically, a partner arr[j] can be paired with arr[i] only when arr[i].cost + arr[j].cost < budget. As i increases (its cost grows), the set of valid partners can only shrink, never grow. This monotonic shrinking behavior is exactly what enables a two-pointer technique.

This brings up a subtlety: when we fix arr[i], we want the partner with the maximum capacity among all valid candidates—but the candidate with the highest capacity is not necessarily the one with the highest cost. Sorting by cost only tells us which machines are affordable as partners; it says nothing about which of those affordable ones has the best capacity. To efficiently retrieve the maximum capacity from a dynamically changing set of valid machines, we maintain an ordered set (remain) keyed by capacity.

Putting these ideas together: we sort by cost, and use pointer i to fix the cheaper machine and pointer j to mark the boundary of affordable partners. Before pairing, we remove arr[i] itself from remain so it cannot pair with itself, and we remove all machines from remain that are now too expensive to pair with arr[i]. Whatever remains in remain is guaranteed to be a valid partner, so we just grab the one with the largest capacity and combine it with arr[i]'s capacity to update the answer. Because both pointers only move forward, each machine is added and removed from remain at most once, giving us an efficient overall solution.

Pattern Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

Solution 1: Sorting + Ordered Set

We first filter out all machines whose cost is strictly less than budget, since any machine with cost >= budget can never be selected (not even on its own). We pair each surviving machine's cost with its capacity and store them in an array arr, where arr[i] = (costs[i], capacity[i]). If arr is empty, no machine can be purchased, so we directly return 0.

Otherwise, we sort arr by cost in ascending order. This sorting is what lets us apply the two-pointer technique later, because once sorted by cost, the set of affordable partners only shrinks as the fixed machine's cost grows.

To handle the single machine case, we initialize the answer with the maximum capacity available among all machines in arr. Since any machine in arr already satisfies the budget on its own, the best single-machine choice is simply the one with the largest capacity.

For the two machine case, we use an ordered set remain to maintain the capacities of all currently available machines. We store entries as (capacity, index) pairs so that ties in capacity are broken by index and the elements stay distinct. Initially, remain holds every machine in arr. The last element remain[-1] always gives us the machine with the maximum capacity in the set.

We then run a two-pointer scan with i starting at the front and j starting at the back:

For each i, we first remove arr[i] from remain (using the entry (arr[i][1], i)), so that machine i cannot be paired with itself.
Next, while i < j and arr[i].cost + arr[j].cost >= budget, the machine at j is too expensive to pair with arr[i]. Since the array is sorted, it is also too expensive for every later (larger-cost) value of i, so we permanently remove arr[j] from remain and move j leftward by doing j -= 1.
After this shrinking step, every machine still in remain is a valid partner for arr[i]. If remain is non-empty, we take the partner with the maximum capacity via remain[-1][0], add it to arr[i]'s capacity, and update the answer with ans = max(ans, arr[i][1] + remain[-1][0]).
Finally, we increment i and continue.

Each machine is added to remain once and removed at most once, so the two pointers together touch each element a constant number of times. The dominant cost comes from sorting and from the ordered-set operations.

The time complexity is O(n × log n), where n is the number of machines, due to the sorting step and the O(log n) insert/remove/query operations on the ordered set. The space complexity is O(n) for storing arr and the remain ordered set.

Example Walkthrough

Let's trace through a concrete example to see how the sorting + ordered set approach works.

Input:

costs = [3, 5, 8, 2]
capacity = [4, 10, 6, 3]
budget = 10

Step 1: Filter machines with cost < budget

We keep only machines whose cost is strictly less than 10:

Original index	cost	capacity	Keep? (cost < 10)
0	3	4	✅
1	5	10	✅
2	8	6	✅
3	2	3	✅

All four survive, giving us arr = [(3,4), (5,10), (8,6), (2,3)].

Step 2: Sort arr by cost ascending

arr = [(2,3), (3,4), (5,10), (8,6)]
       i=0    i=1    i=2     i=3

Step 3: Initialize answer with the best single machine

The largest capacity among all valid machines is 10 (from machine (5,10)). Since every machine here already fits the budget alone, the best single-machine choice gives:

ans = 10

Step 4: Build the ordered set remain keyed by (capacity, index):

remain = { (3,0), (4,1), (10,2), (6,3) }
remain[-1] = (10,2)   // max capacity = 10

Step 5: Two-pointer scan with i = 0, j = 3.

Iteration i = 0, machine arr[0] = (2,3) (cost 2):

Remove itself (3,0) from remain → remain = { (4,1), (6,3), (10,2) }
Check j = 3: arr[0].cost + arr[3].cost = 2 + 8 = 10, which is not < 10 (it equals budget). Too expensive → remove arr[3] entry (6,3), do j -= 1 → j = 2.
- remain = { (4,1), (10,2) }
Check j = 2: 2 + 5 = 7 < 10 ✅ valid. Stop shrinking.
Best partner = remain[-1][0] = 10. Update: ans = max(10, 3 + 10) = 13.
i = 1

Iteration i = 1, machine arr[1] = (3,4) (cost 3):

Remove itself (4,1) from remain → remain = { (10,2) }
Check i < j → 1 < 2 ✅. arr[1].cost + arr[2].cost = 3 + 5 = 8 < 10 ✅ valid. No shrinking.
Best partner = remain[-1][0] = 10. Update: ans = max(13, 4 + 10) = 14.
i = 2

Iteration i = 2, machine arr[2] = (5,10) (cost 5):

Remove itself (10,2) from remain → remain = { } (empty)
Now i < j is 2 < 2 → false, so no shrinking.
remain is empty → no valid partner, skip update.
i = 3

Iteration i = 3: i = 3 is not < j = 2, loop ends.

Result:

ans = 14

The optimal choice is pairing machine (3,4) with machine (5,10): total cost 3 + 5 = 8 < 10, total capacity 4 + 10 = 14. This beats both the best single machine (10) and the pairing found earlier (13), confirming the answer.

Solution Implementation

1from typing import List
2from sortedcontainers import SortedList
3
4
5class Solution:
6    def maxCapacity(self, costs: List[int], capacity: List[int], budget: int) -> int:
7        # Keep only items whose individual cost is below the budget,
8        # since any item costing >= budget can never be selected.
9        affordable_items = []
10        for cost, cap in zip(costs, capacity):
11            if cost < budget:
12                affordable_items.append((cost, cap))
13
14        # No item fits within the budget at all.
15        if not affordable_items:
16            return 0
17
18        # Sort items by ascending cost so we can use two pointers.
19        affordable_items.sort()
20
21        # SortedList of (capacity, index) representing items still available
22        # to be paired as the "second" chosen item.
23        available = SortedList()
24        for index, (_cost, cap) in enumerate(affordable_items):
25            available.add((cap, index))
26
27        left, right = 0, len(affordable_items) - 1
28
29        # Baseline answer: picking the single item with the largest capacity.
30        best = available[-1][0]
31
32        while left < right:
33            # The current left item is now being treated as the "first" item,
34            # so remove it from the pool of candidate "second" items.
35            available.discard((affordable_items[left][1], left))
36
37            # Shrink the right pointer while the cheapest (left) item combined
38            # with the most expensive (right) item exceeds the budget.
39            while left < right and affordable_items[left][0] + affordable_items[right][0] >= budget:
40                available.discard((affordable_items[right][1], right))
41                right -= 1
42
43            # Pair the left item's capacity with the best remaining capacity.
44            if available:
45                best = max(best, affordable_items[left][1] + available[-1][0])
46
47            left += 1
48
49        return best
50

1class Solution {
2    public int maxCapacity(int[] costs, int[] capacity, int budget) {
3        // Step 1: Keep only items whose individual cost is below the budget.
4        // Each entry stores {cost, capacity}.
5        List<int[]> items = new ArrayList<>();
6        for (int index = 0; index < costs.length; index++) {
7            int cost = costs[index];
8            int cap = capacity[index];
9            if (cost < budget) {
10                items.add(new int[] {cost, cap});
11            }
12        }
13
14        // If no item is affordable, nothing can be selected.
15        if (items.isEmpty()) {
16            return 0;
17        }
18
19        // Step 2: Sort the affordable items by ascending cost,
20        // so two-pointer scanning over cost becomes possible.
21        items.sort(Comparator.comparingInt(item -> item[0]));
22
23        // Step 3: Maintain a TreeSet ordered by capacity (then by index as a tie-breaker).
24        // Each entry stores {capacity, indexInSortedItems}.
25        // This lets us quickly query the maximum remaining capacity.
26        TreeSet<int[]> remaining = new TreeSet<>((first, second) -> {
27            if (first[0] != second[0]) {
28                return first[0] - second[0]; // order by capacity
29            }
30            return first[1] - second[1];     // tie-break by index
31        });
32        for (int index = 0; index < items.size(); index++) {
33            remaining.add(new int[] {items.get(index)[1], index});
34        }
35
36        // Step 4: Two-pointer scan.
37        int left = 0;
38        int right = items.size() - 1;
39
40        // Initialize the answer with the largest available capacity
41        // (covers the single-item / self-pair baseline case).
42        int answer = remaining.last()[0];
43
44        while (left < right) {
45            // The current left item is the one we are pairing; remove it from the pool
46            // so it isn't double-counted as the "remaining best capacity".
47            remaining.remove(new int[] {items.get(left)[1], left});
48
49            // Shrink the right side while the combined cost is too high (>= budget).
50            // Those right items can never pair with this (or any larger) left item.
51            while (left < right && items.get(left)[0] + items.get(right)[0] >= budget) {
52                remaining.remove(new int[] {items.get(right)[1], right});
53                right--;
54            }
55
56            // Among the still-valid items, take the largest remaining capacity
57            // and combine it with the current left item's capacity.
58            if (!remaining.isEmpty()) {
59                answer = Math.max(answer, items.get(left)[1] + remaining.last()[0]);
60            }
61
62            // Move to the next left item.
63            left++;
64        }
65
66        return answer;
67    }
68}
69

1class Solution {
2public:
3    int maxCapacity(vector<int>& costs, vector<int>& capacity, int budget) {
4        // Store (cost, capacity) pairs for items that can be afforded
5        // alongside at least one other item (cost strictly less than budget).
6        vector<pair<int, int>> items;
7        for (int k = 0; k < static_cast<int>(costs.size()); k++) {
8            int cost = costs[k];
9            int cap = capacity[k];
10            if (cost < budget) {
11                items.emplace_back(cost, cap);
12            }
13        }
14
15        // No affordable item means no capacity can be obtained.
16        if (items.empty()) {
17            return 0;
18        }
19
20        // Sort items by cost in ascending order so we can use a two-pointer
21        // sweep over the cost dimension.
22        sort(items.begin(), items.end());
23
24        // Multiset keyed on (capacity, index) lets us quickly query the
25        // maximum capacity among the items still available to pair with.
26        multiset<pair<int, int>> available;
27        for (int idx = 0; idx < static_cast<int>(items.size()); idx++) {
28            available.insert({items[idx].second, idx});
29        }
30
31        int left = 0;
32        int right = static_cast<int>(items.size()) - 1;
33
34        // Initialize the answer with the single largest capacity available.
35        int ans = prev(available.end())->first;
36
37        // Two-pointer sweep: for each left item, find the best partner.
38        while (left < right) {
39            // The current left item cannot be paired with itself, so remove it.
40            available.erase(available.find({items[left].second, left}));
41
42            // Shrink the right boundary while the pair's total cost exceeds
43            // the budget; those right items are unaffordable together with left.
44            while (left < right && items[left].first + items[right].first >= budget) {
45                available.erase(available.find({items[right].second, right}));
46                right--;
47            }
48
49            // If any partner remains, combine the left item's capacity with the
50            // largest remaining capacity to update the best answer.
51            if (!available.empty()) {
52                ans = max(ans, items[left].second + prev(available.end())->first);
53            }
54
55            left++;
56        }
57
58        return ans;
59    }
60};
61

1/**
2 * Two-pointer sweep to find the maximum combined capacity of two affordable
3 * items whose total cost stays strictly under the given budget.
4 *
5 * @param costs    Cost of each item.
6 * @param capacity Capacity of each item.
7 * @param budget   Total budget available; a pair's cost must be < budget.
8 * @returns        The best achievable capacity (single item or a valid pair).
9 */
10function maxCapacity(costs: number[], capacity: number[], budget: number): number {
11    // Store (cost, capacity) pairs for items that can be afforded alongside
12    // at least one other item (cost strictly less than budget).
13    const items: Array<[number, number]> = [];
14    for (let k = 0; k < costs.length; k++) {
15        const cost = costs[k];
16        const cap = capacity[k];
17        if (cost < budget) {
18            items.push([cost, cap]);
19        }
20    }
21
22    // No affordable item means no capacity can be obtained.
23    if (items.length === 0) {
24        return 0;
25    }
26
27    // Sort items by cost in ascending order so we can use a two-pointer
28    // sweep over the cost dimension.
29    items.sort((a, b) => a[0] - b[0]);
30
31    const n = items.length;
32
33    // Build a sparse table over capacities to answer range-maximum queries.
34    // After all removals in the sweep, the "available" set is always the
35    // contiguous index window [left + 1, right], so range-max over capacities
36    // reproduces the multiset's max-capacity query in O(1) per lookup.
37    const LOG = Math.floor(Math.log2(n)) + 1;
38    const sparse: number[][] = Array.from({ length: LOG }, () => new Array<number>(n).fill(0));
39    for (let i = 0; i < n; i++) {
40        sparse[0][i] = items[i][1];
41    }
42    for (let j = 1; j < LOG; j++) {
43        for (let i = 0; i + (1 << j) <= n; i++) {
44            sparse[j][i] = Math.max(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]);
45        }
46    }
47
48    // Query the maximum capacity within the inclusive index range [lo, hi].
49    const rangeMax = (lo: number, hi: number): number => {
50        if (lo > hi) {
51            return -Infinity;
52        }
53        const k = Math.floor(Math.log2(hi - lo + 1));
54        return Math.max(sparse[k][lo], sparse[k][hi - (1 << k) + 1]);
55    };
56
57    let left = 0;
58    let right = n - 1;
59
60    // Initialize the answer with the single largest capacity available.
61    let ans = rangeMax(0, n - 1);
62
63    // Two-pointer sweep: for each left item, find the best partner.
64    while (left < right) {
65        // Shrink the right boundary while the pair's total cost exceeds the
66        // budget; those right items are unaffordable together with left.
67        while (left < right && items[left][0] + items[right][0] >= budget) {
68            right--;
69        }
70
71        // The partners available for the current left item are the items in
72        // the window [left + 1, right]; combine the best one with left.
73        if (left < right) {
74            ans = Math.max(ans, items[left][1] + rangeMax(left + 1, right));
75        }
76
77        left++;
78    }
79
80    return ans;
81}
82

Time and Space Complexity

Time Complexity: O(n log n), where n is the number of machines.

The analysis proceeds step by step:
- Building the filtered list arr by iterating over costs and capacity with zip takes O(n).
- Sorting arr takes O(n log n).
- Initializing the SortedList by adding n elements costs O(n log n), since each insertion into a SortedList is O(log n) (amortized).
- The two-pointer while i < j loop runs at most O(n) iterations in total (each of i and j moves monotonically). Inside the loop, each discard operation on the SortedList costs O(log n), and each element is discarded at most once, so the total cost of all discard calls is O(n log n). Accessing remain[-1] is O(log n) per access.
Combining all parts, the dominant term is O(n log n).
Space Complexity: O(n), where n is the number of machines.

The auxiliary arr list stores up to n tuples, and the SortedList remain also holds up to n elements. Both grow linearly with the input size, so the overall extra space is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing the cost index and the capacity index when discarding from the ordered set

The most error-prone part of this solution is the bookkeeping inside the SortedList. Each entry is stored as (capacity, index), not (cost, capacity). When you remove the left item from the candidate pool, it is tempting to write something like:

available.discard((affordable_items[left][0], left))   # WRONG: uses cost, not capacity

But affordable_items[left][0] is the cost, while the set was populated with capacity as the first field. Discarding the wrong tuple silently fails (discard does nothing if the element is absent), leaving the "first" item still in the pool. The algorithm may then pair an item with itself, producing an answer that doubles a single machine's capacity.

Solution: Always discard with the same key you inserted with — the capacity, paired with the index:

available.discard((affordable_items[left][1], left))   # CORRECT: capacity + index

Including the index in the tuple is what guarantees uniqueness so the correct entry is removed even when two machines share the same capacity.

Pitfall 2: Using `>` instead of `>=` in the budget comparison

The problem requires the combined cost to be strictly less than budget. The shrinking condition is:

while left < right and affordable_items[left][0] + affordable_items[right][0] >= budget:

If you mistakenly write > budget, then a pair whose cost exactly equals budget would be accepted, violating the "strictly less" requirement and overcounting capacity. Likewise, the initial filtering uses cost < budget (not <=) for the single-machine case for the same reason.

Solution: Keep the strict-inequality semantics consistent everywhere:

Single-machine filter: cost < budget
Two-machine rejection: cost_left + cost_right >= budget (reject equality).

Pitfall 3: Forgetting the single-machine baseline

It is easy to focus only on the two-machine pairing and forget that selecting one machine is also valid. If n == 1, or if every pair exceeds the budget while individual machines fit, the two-pointer loop may never update best.

best = available[-1][0]   # baseline: the single largest-capacity affordable item

Solution: Initialize best with the maximum capacity among all affordable items before the loop. Because every item in affordable_items already satisfies cost < budget, the largest-capacity one is always a legal single-machine choice. Returning 0 only when affordable_items is empty covers the "nothing affordable" case.

Pitfall 4: Removing right-pointer items but later re-needing them for a smaller `left`

A subtle concern is whether permanently discarding arr[right] is safe. One might worry that a later iteration with a different left could benefit from a previously removed right item.

This is not a bug here, but the reasoning must be understood: the array is sorted by ascending cost. When arr[left] + arr[right] >= budget, every subsequent left has a larger cost, so the same right item remains unaffordable. Thus discarding it permanently is correct.

Solution: Rely on the sorted order. If you ever reorder the iteration (e.g., iterate left from large to small), this monotonicity breaks and the permanent removal becomes invalid — so do not change the scan direction without revisiting the pruning logic.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering