{x}
blog image

Maximum Number of Robots Within Budget

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

Solution Explanation: Maximum Number of Robots Within Budget

This problem asks to find the maximum number of consecutive robots that can be run within a given budget. The cost of running k robots is max(chargeTimes) + k * sum(runningCosts). This suggests a sliding window approach combined with efficient tracking of the maximum charge time within the window.

Approach:

The solution uses a two-pointer sliding window approach along with a monotonic decreasing deque to efficiently track the maximum charge time.

  1. Sliding Window: We maintain a sliding window of consecutive robots. The left and right pointers (l and r) define the window's boundaries.

  2. Prefix Sum: We use a running sum (s) to calculate the sum of runningCosts within the current window efficiently. Updating the sum as the window slides is O(1).

  3. Monotonic Decreasing Deque: A deque q stores the indices of robots, maintaining a decreasing order of chargeTimes. This deque ensures that the maximum chargeTime within the current window is always at the front (q[0]). This is crucial for O(1) access to the maximum charge time. When a new robot is added to the window, we pop elements from the back of q whose chargeTimes are less than or equal to the new robot's chargeTime. When a robot is removed from the window's left side (because the window is sliding), we pop elements from the front of q if they are outside the current window.

  4. Cost Calculation: For each window size, we calculate the total cost: max(chargeTimes) + k * sum(runningCosts). The max(chargeTimes) is efficiently obtained from chargeTimes[q[0]].

  5. Budget Check: We check if the total cost exceeds the budget. If it does, we shrink the window from the left until the cost is within the budget.

  6. Maximum Consecutive Robots: The maximum number of consecutive robots within the budget is tracked in the variable ans.

Time Complexity Analysis:

  • The outer loop iterates through each robot once, taking O(n) time.
  • The deque operations (push and pop) take O(1) amortized time.
  • The inner loop (shrinking the window) iterates at most n times in total across all iterations of the outer loop because l only increases.

Therefore, the overall time complexity is O(n).

Space Complexity Analysis:

  • The deque q stores at most n elements in the worst case.
  • The space used by other variables is constant.

Therefore, the overall space complexity is O(n).

Code Examples (Python, Java, C++, Go, TypeScript): The code examples in the original response demonstrate this algorithm effectively. Each language's nuances are handled appropriately in the respective implementations. The Go example includes a custom implementation of a deque data structure using slices for flexibility. The TypeScript example includes a custom implementation of a doubly-linked list based deque. These are commonly used data structures that effectively support the required operations in O(1) time.