Watch 10 video solutions for Maximum Number of Robots Within Budget, a hard level problem involving Array, Binary Search, Queue. This walkthrough by Code with Alisha has 3,552 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |