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 <= 1015This 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.
C++
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.
C#
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.
| 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. |
Maximum Number of Balloons - Leetcode 1189 - Python • NeetCode • 25,417 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