# Maximum Number of Robots Within Budget **Difficulty:** HARD [External](https://leetcode.com/problems/maximum-number-of-robots-within-budget) Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-robots-within-budget **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum) **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) **Data structures:** Array, Heap (Priority Queue), Queue, Monotonic Queue **Companies:** [InMobi](https://scaleengineer.com/companies/inmobi) --- ## Problem 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 == n` * `1 <= n <= 5 * 104` * `1 <= chargeTimes[i], runningCosts[i] <= 105` * `1 <= budget <= 1015` # Approaches ## Brute Force 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. **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. **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. ### Explanation 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. ```java 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; } } ``` ### 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 (from `k = i` to `j`) to: - Find the maximum `chargeTime` in the subarray. - Calculate the sum of `runningCosts` in the subarray. - Calculate the total cost using the formula: `cost = max(chargeTimes) + (j - i + 1) * sum(runningCosts)`. - If `cost <= budget`, update `maxLength = max(maxLength, j - i + 1)`. - After all subarrays are checked, return `maxLength`. ## Optimized Brute Force 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. **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. **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'. ### Explanation 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. ```java 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; } } ``` ### 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 indices `j` from `i` to `n-1`. - Maintain a `currentSum` of `runningCosts` and a `currentMax` of `chargeTimes` for the window `[i, j]`. - As `j` increments, update `currentSum` and `currentMax` in O(1) time. - Calculate the cost for the window `[i, j]`. - If the cost is within budget, update `maxLength`. - Return `maxLength`. ## Binary Search on the Answer 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. **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. **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. ### Explanation 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. ```java 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 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; } } ``` ### Algorithm - The core idea is that if we can run `k` robots, we can also run any number of robots less than `k`. 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 `mid` value of `k` in the binary search, create a helper function `isPossible(k)` to check if there's *any* consecutive subarray of size `k` that meets the budget. - If `isPossible(k)` is true, it means `k` is a possible answer, so we try for a larger `k` by setting `low = k + 1` and save `k` as a potential result. - If `isPossible(k)` is false, `k` is too large, so we search in the lower half by setting `high = 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 `k` for which `isPossible(k)` was true. ## Optimal Sliding Window with Deque 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. **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. **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. ### Explanation 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. ```java 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 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; } } ``` ### Algorithm - Initialize two pointers, `left = 0` and `right = 0`, to represent the sliding window `[left, right]`. - Initialize `currentSum = 0` for `runningCosts` and a deque `maxDeque` to track the maximum `chargeTime`. - Iterate `right` from `0` to `n-1` to expand the window. - Add `runningCosts[right]` to `currentSum`. - Update the `maxDeque` by removing elements from the tail that are smaller than or equal to `chargeTimes[right]`, then add `right` to the tail. This keeps the deque monotonically decreasing. - After expanding, check the cost of the current window: `cost = chargeTimes[maxDeque.peekFirst()] + (right - left + 1) * currentSum`. - While `cost > budget` and `left <= right`, shrink the window from the left: - Subtract `runningCosts[left]` from `currentSum`. - If the leftmost element was the maximum (i.e., `maxDeque.peekFirst() == left`), remove it from the deque. - Increment `left`. - After each step of the `right` pointer (and potential shrinking), the window `[left, right]` is valid. Update `maxLength = max(maxLength, right - left + 1)`. - Return `maxLength`. # Solutions ### Java ```java class Solution { public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) { Deque 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; } } ``` ### CPP ```cpp class Solution { public: int maximumRobots(vector &chargeTimes, vector &runningCosts, long long budget) { deque 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; } }; ``` ### Python ```python 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 ans ```