Maximum Number of Robots Within Budget
HardPrompt
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 <= 1015
Approaches
4 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward way to solve the problem. It involves checking every single possible consecutive subarray of robots. For each subarray, it calculates the total cost from scratch and compares it with the given budget. The length of the longest valid subarray found is the answer.
Algorithm
- Initialize
maxLength = 0. - Use a nested loop to iterate through all possible start (
i) and end (j) indices of a consecutive subarray. - For each subarray
[i, j], use a third loop (fromk = itoj) to:- Find the maximum
chargeTimein the subarray. - Calculate the sum of
runningCostsin the subarray.
- Find the maximum
- Calculate the total cost using the formula:
cost = max(chargeTimes) + (j - i + 1) * sum(runningCosts). - If
cost <= budget, updatemaxLength = max(maxLength, j - i + 1). - After all subarrays are checked, return
maxLength.
Walkthrough
This method systematically generates all consecutive subarrays. A subarray is defined by its starting index i and ending index j. We use two nested loops for i and j to define the window. Inside these loops, a third loop iterates from i to j to compute the necessary components for the cost calculation: the maximum chargeTime and the sum of runningCosts within that specific subarray. After computing these values, the total cost is calculated. If this cost is within the budget, we compare the current subarray's length with the maximum length found so far and update it if necessary. This process is repeated until all n * (n + 1) / 2 subarrays have been evaluated.
class Solution { public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) { int n = chargeTimes.length; int maxLength = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { long maxCharge = 0; long sumRunning = 0; // Innermost loop to calculate max and sum for subarray [i, j] for (int k = i; k <= j; k++) { maxCharge = Math.max(maxCharge, chargeTimes[k]); sumRunning += runningCosts[k]; } int len = j - i + 1; // Use long for cost calculation to avoid overflow long totalCost = maxCharge + (long)len * sumRunning; if (totalCost <= budget) { maxLength = Math.max(maxLength, len); } } } return maxLength; }}Complexity
Time
O(n^3) - There are three nested loops. The outer two loops iterate through all O(n^2) subarrays, and the inner loop takes O(n) time to compute the sum and maximum for each subarray.
Space
O(1) - We only use a few variables to store the maximum length, current max charge, and current sum, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Requires no complex data structures.
Cons
Extremely inefficient due to the cubic time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
This approach is an optimization of the naive brute-force method. Instead of recalculating the sum of runningCosts and the maximum chargeTime for every subarray, we can maintain these values as we expand the subarray. This eliminates the innermost loop, improving the time complexity.
Algorithm
- Initialize
maxLength = 0. - Use an outer loop to iterate through all possible start indices
i. - For each
i, use an inner loop to iterate through all possible end indicesjfromiton-1. - Maintain a
currentSumofrunningCostsand acurrentMaxofchargeTimesfor the window[i, j]. - As
jincrements, updatecurrentSumandcurrentMaxin O(1) time. - Calculate the cost for the window
[i, j]. - If the cost is within budget, update
maxLength. - Return
maxLength.
Walkthrough
We iterate through each possible starting point i of a subarray. For each i, we start building a subarray by iterating j from i to the end of the array. We maintain two variables: currentSumRunning for the sum of runningCosts and currentMaxCharge for the maximum chargeTime in the current window [i, j]. When we extend the window from j to j+1, we can update currentSumRunning by simply adding runningCosts[j+1] and currentMaxCharge by taking max(currentMaxCharge, chargeTimes[j+1]). This update takes constant time. For each valid window [i, j], we calculate the cost and update our maximum length if the cost is within budget.
class Solution { public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) { int n = chargeTimes.length; int maxLength = 0; for (int i = 0; i < n; i++) { long currentMaxCharge = 0; long currentSumRunning = 0; for (int j = i; j < n; j++) { currentMaxCharge = Math.max(currentMaxCharge, chargeTimes[j]); currentSumRunning += runningCosts[j]; int k = j - i + 1; long totalCost = currentMaxCharge + (long)k * currentSumRunning; if (totalCost <= budget) { maxLength = Math.max(maxLength, k); } else { // Optimization: if cost for [i,j] > budget, cost for [i, j+1] will also be > budget break; } } } return maxLength; }}Complexity
Time
O(n^2) - Two nested loops are used to check all subarrays, with O(1) work inside the inner loop.
Space
O(1) - Constant extra space is used.
Trade-offs
Pros
A significant improvement over the O(n^3) approach.
Still relatively easy to reason about.
Cons
Still too slow for the given constraints, leading to 'Time Limit Exceeded'.
A more efficient approach involves performing a binary search on the answer (the maximum number of robots k). For a given k, we can efficiently check if it's possible to find any consecutive subarray of that length that satisfies the budget. This check can be done in linear time using a sliding window.
Algorithm
- The core idea is that if we can run
krobots, we can also run any number of robots less thank. This monotonic property allows for binary search on the answer. - Binary search for the answer
k(the number of robots) in the range[0, n]. - For each
midvalue ofkin the binary search, create a helper functionisPossible(k)to check if there's any consecutive subarray of sizekthat meets the budget. - If
isPossible(k)is true, it meanskis a possible answer, so we try for a largerkby settinglow = k + 1and savekas a potential result. - If
isPossible(k)is false,kis too large, so we search in the lower half by settinghigh = k - 1. - The
isPossible(k)function is implemented in O(n) using a fixed-size sliding window and a deque to find the window maximum efficiently. - Return the largest
kfor whichisPossible(k)was true.
Walkthrough
We can observe that the feasibility of running k robots is monotonic. If a window of size k is valid, any sub-window of size k-1 within it will also be valid because all terms in the cost function (max, k, sum) will be smaller or equal. This allows us to binary search for the maximum valid k.
The search space is [0, n]. For each candidate length k, we need to verify if there exists at least one subarray of length k that is within budget. This verification, isPossible(k), is done using a sliding window of fixed size k. As we slide this window across the arrays, we maintain the sum of runningCosts and use a deque to find the maximum chargeTime in the current window in O(1) amortized time. If we find any such window, isPossible(k) returns true. The binary search then adjusts its range based on this result.
import java.util.ArrayDeque;import java.util.Deque; class Solution { public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) { int n = chargeTimes.length; int low = 0, high = n; int ans = 0; while (low <= high) { int k = low + (high - low) / 2; if (k == 0) { low = k + 1; continue; } if (isPossible(k, chargeTimes, runningCosts, budget)) { ans = k; low = k + 1; } else { high = k - 1; } } return ans; } private boolean isPossible(int k, int[] chargeTimes, int[] runningCosts, long budget) { long currentSum = 0; Deque<Integer> maxDeque = new ArrayDeque<>(); for (int i = 0; i < chargeTimes.length; i++) { currentSum += runningCosts[i]; while (!maxDeque.isEmpty() && chargeTimes[maxDeque.peekLast()] <= chargeTimes[i]) { maxDeque.pollLast(); } maxDeque.offerLast(i); if (i >= k - 1) { long maxCharge = chargeTimes[maxDeque.peekFirst()]; if (maxCharge + (long)k * currentSum <= budget) { return true; } currentSum -= runningCosts[i - k + 1]; if (maxDeque.peekFirst() == i - k + 1) { maxDeque.pollFirst(); } } } return false; }}Complexity
Time
O(n log n) - The binary search performs O(log n) iterations, and each call to `isPossible(k)` takes O(n) time.
Space
O(n) - The deque in the `isPossible` function can store up to `k` indices, where `k` can be up to `n` in the worst case.
Trade-offs
Pros
Much more efficient than O(n^2) approaches.
Guaranteed to pass within the time limits.
Cons
Slightly more complex due to the combination of binary search and a sliding window helper function.
Not the most optimal solution as a pure O(n) approach exists.
The most optimal solution uses a sliding window approach with two pointers, left and right. The window [left, right] represents the group of consecutive robots. We expand the window by moving right and shrink it by moving left whenever the budget is exceeded. A deque is used to efficiently track the maximum chargeTime within the current window.
Algorithm
- Initialize two pointers,
left = 0andright = 0, to represent the sliding window[left, right]. - Initialize
currentSum = 0forrunningCostsand a dequemaxDequeto track the maximumchargeTime. - Iterate
rightfrom0ton-1to expand the window.- Add
runningCosts[right]tocurrentSum. - Update the
maxDequeby removing elements from the tail that are smaller than or equal tochargeTimes[right], then addrightto the tail. This keeps the deque monotonically decreasing.
- Add
- After expanding, check the cost of the current window:
cost = chargeTimes[maxDeque.peekFirst()] + (right - left + 1) * currentSum. - While
cost > budgetandleft <= right, shrink the window from the left:- Subtract
runningCosts[left]fromcurrentSum. - If the leftmost element was the maximum (i.e.,
maxDeque.peekFirst() == left), remove it from the deque. - Increment
left.
- Subtract
- After each step of the
rightpointer (and potential shrinking), the window[left, right]is valid. UpdatemaxLength = max(maxLength, right - left + 1). - Return
maxLength.
Walkthrough
This approach avoids redundant calculations by maintaining a single, variable-sized window. We use a right pointer to iterate through the array, adding one robot at a time to the window. We maintain the sum of runningCosts in O(1) time. The main challenge, finding the maximum chargeTime in the window efficiently, is solved using a monotonically decreasing deque. The deque stores indices from chargeTimes, such that the values at these indices are in decreasing order. This ensures chargeTimes[deque.peekFirst()] is always the maximum in the current window.
For each position of right, we add the new robot and calculate the cost. If the cost exceeds the budget, we must shrink the window from the left. We increment the left pointer, remove its contributions from the currentSum, and update the deque if left was the index of the max element. We repeat this shrinking process until the window's cost is within budget. At each step, the size of the valid window (right - left + 1) is a candidate for the answer, and we keep track of the maximum size found.
import java.util.ArrayDeque;import java.util.Deque; class Solution { public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) { int n = chargeTimes.length; int left = 0; int maxLength = 0; long currentSum = 0; Deque<Integer> maxDeque = new ArrayDeque<>(); for (int right = 0; right < n; right++) { currentSum += runningCosts[right]; while (!maxDeque.isEmpty() && chargeTimes[maxDeque.peekLast()] <= chargeTimes[right]) { maxDeque.pollLast(); } maxDeque.offerLast(right); // Shrink window if budget is exceeded while (!maxDeque.isEmpty() && chargeTimes[maxDeque.peekFirst()] + (long)(right - left + 1) * currentSum > budget) { // Remove left element's contribution if (maxDeque.peekFirst() == left) { maxDeque.pollFirst(); } currentSum -= runningCosts[left]; left++; } maxLength = Math.max(maxLength, right - left + 1); } return maxLength; }}Complexity
Time
O(n) - Both the `left` and `right` pointers traverse the array at most once. Each element is added to and removed from the deque at most once, leading to amortized O(1) operations per step.
Space
O(n) - In the worst-case scenario (e.g., a strictly decreasing `chargeTimes` array), the deque could store up to `n` indices.
Trade-offs
Pros
Most efficient solution with a linear time complexity.
Processes each element a constant number of times.
Cons
The logic, especially with the deque and the shrinking condition, can be more complex to implement correctly than simpler approaches.
Solutions
Solution
class Solution {public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) { Deque<Integer> q = new ArrayDeque<>(); int n = chargeTimes.length; long s = 0; int j = 0; int ans = 0; for (int i = 0; i < n; ++i) { int a = chargeTimes[i], b = runningCosts[i]; while (!q.isEmpty() && chargeTimes[q.getLast()] <= a) { q.pollLast(); } q.offer(i); s += b; while (!q.isEmpty() && chargeTimes[q.getFirst()] + (i - j + 1) * s > budget) { if (q.getFirst() == j) { q.pollFirst(); } s -= runningCosts[j++]; } ans = Math.max(ans, i - j + 1); } return ans; }}class Solution {public: int maximumRobots(vector<int> &chargeTimes, vector<int> &runningCosts, long long budget) { deque<int> q; long long s = 0; int ans = 0, j = 0, n = chargeTimes.size(); for (int i = 0; i < n; ++i) { int a = chargeTimes[i], b = runningCosts[i]; while (!q.empty() && chargeTimes[q.back()] <= a) q.pop_back(); q.push_back(i); s += b; while (!q.empty() && chargeTimes[q.front()] + (i - j + 1) * s > budget) { if (q.front() == j) { q.pop_front(); } s -= runningCosts[j++]; } ans = max(ans, i - j + 1); } return ans; }};class Solution: def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int: q = deque() ans = j = s = 0 for i, (a, b) in enumerate(zip(chargeTimes, runningCosts)): while q and chargeTimes[q[- 1]] <= a: q . pop() q . append(i) s += b while q and chargeTimes[q[0]] + (i - j + 1) * s > budget: if q[0] == j: q . popleft() s -= runningCosts[j] j += 1 ans = max(ans, i - j + 1) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.