You have n robots. You are given two 0-indexed integer arrays, chargeTimes and runningCosts, both of length n. The ith robot costs chargeTimes[i] units to charge and costs runningCosts[i] units to run. You are also given an integer budget.
The total cost of running k chosen robots is equal to max(chargeTimes) + k * sum(runningCosts), where max(chargeTimes) is the largest charge cost among the k robots and sum(runningCosts) is the sum of running costs among the k robots.
Return the maximum number of consecutive robots you can run such that the total cost does not exceed budget.
Example 1:
Input: chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25 Output: 3 Explanation: It is possible to run all individual and consecutive pairs of robots within budget. To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 which is less than 25. It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.
Example 2:
Input: chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19 Output: 0 Explanation: No robot can be run that does not exceed the budget, so we return 0.
Constraints:
chargeTimes.length == runningCosts.length == n1 <= n <= 5 * 1041 <= chargeTimes[i], runningCosts[i] <= 1051 <= budget <= 1015Problem Overview: You are given two arrays representing robot chargeTimes and runningCosts. Running k robots costs max(chargeTimes in window) + k * sum(runningCosts in window). The task is to find the largest group of consecutive robots that can run without exceeding the given budget.
Approach 1: Sliding Window with Monotonic Deque (O(n) time, O(n) space)
This is the optimal solution and relies on a sliding window combined with a monotonic queue. Expand the right pointer to include more robots while maintaining the sum of runningCosts. A deque keeps indices of robots in decreasing order of chargeTimes, so the front always holds the maximum charge time in the current window. Each time the window grows, compute the cost using maxCharge + windowSize * runningCostSum. If the cost exceeds the budget, move the left pointer forward and update the structures. Every element enters and leaves the deque at most once, giving linear time complexity. This approach works well because it efficiently tracks the maximum value while dynamically adjusting the window.
Approach 2: Binary Search with Prefix Sum (O(n log n) time, O(n) space)
This approach searches for the maximum valid window size using binary search. For a candidate size k, check if any subarray of length k satisfies the budget constraint. A prefix sum array allows constant-time computation of the sum of runningCosts for any window. To evaluate the maximum chargeTimes within each window, maintain a deque that stores indices in decreasing order, similar to the sliding window maximum technique. If at least one window of size k meets the budget condition, increase the search range; otherwise decrease it. Binary search narrows down the largest feasible window length.
Recommended for interviews: Interviewers typically expect the sliding window + monotonic deque solution. It demonstrates strong understanding of window expansion, maintaining dynamic maximum values, and amortized O(n) processing. The binary search approach is also valid and easier to reason about for some candidates, but the linear-time sliding window solution shows deeper algorithmic skill.
This approach involves using a sliding window technique along with a deque to maintain the maximum charge time within the current window. The goal is to efficiently manage the constraints such as recalculating the maximum value without iterating over the entire window each time.
We slide a window (i.e., a contiguous subarray) over the robots. The window expands by including a new robot, and contracts when the budget constraint is violated. Within this window, the max function and the sum function are used to compute the total cost. The sliding window and deque help manage the max charge time efficiently by allowing for constant-time insertion and removal of the charge times.
This Python function uses a deque to track the indices of chargeTimes for which we need to calculate the maximum effectively within a sliding window. The window's total running cost and the maximum charge time (determined by deque) are used to confirm whether the current set of robots fits within the given budget.
The time complexity is O(n) because each element is processed at most twice by deque operations (once when added, once when removed). The space complexity is O(k) where k is the maximum number of elements that can fit in the deque, which is bounded by the number of robots.
This approach uses binary search to find the maximum size of subarrays where the cost does not exceed the budget. The idea is to use a combination of binary search and prefix sums to evaluate whether it's possible to run a specific number of robots simultaneously without exceeding the budget. For each midpoint in the binary search, you need to check possible windows using prefix sum calculations.
This Java solution applies a combination of binary search to find the maximum number of robots and uses deque within a helper function to manage the sliding window size of robots we are evaluating.
The binary search part has a time complexity of O(log n), and for each mid calculation, the cost checks take O(n), leading to a total complexity of O(n log n). The space complexity is O(n) due to the use of the runningCostsPrefix array and deque.
The problem is essentially finding the maximum value within a sliding window, which can be solved using a monotonic queue.
We only need to use binary search to enumerate the size of the window k, and find the largest k that satisfies the problem requirements.
In the implementation process, we don't actually need to perform binary search enumeration. We just need to change the fixed window to a non-fixed window with double pointers.
The time complexity is O(n), and the space complexity is O(n), where n is the number of robots in the problem.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sliding Window with Deque for Maximum | The time complexity is O(n) because each element is processed at most twice by deque operations (once when added, once when removed). The space complexity is O(k) where k is the maximum number of elements that can fit in the deque, which is bounded by the number of robots. |
| Approach 2: Binary Search with Prefix Sum | The binary search part has a time complexity of O(log n), and for each mid calculation, the cost checks take O(n), leading to a total complexity of O(n log n). The space complexity is O(n) due to the use of the runningCostsPrefix array and deque. |
| Two Pointers + Monotonic Queue | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Monotonic Deque | O(n) | O(n) | Best overall solution. Efficient when scanning the array once while maintaining the maximum charge time. |
| Binary Search with Prefix Sum | O(n log n) | O(n) | Useful when reasoning about window size feasibility or when applying binary search on the answer. |
Leetcode 2398. Maximum Number of Robots Within Budget | Biweekly Contest 86. | Hard | Most Optimal • Code with Alisha • 3,552 views views
Watch 9 more video solutions →Practice Maximum Number of Robots Within Budget with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor