#2398

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Number of Robots Within Budget

Determine the maximum number of consecutive robots you can operate without exceeding a given budget using efficient binary search techniques.

array binary search queue sliding window heap priority queue

Problem Statement

You are given n robots, each with a charge cost and a running cost. The charge costs are stored in array chargeTimes and the running costs in array runningCosts, both of length n. A total budget is provided, representing the maximum combined cost you can spend on consecutive robots.

The total cost to run k consecutive robots is computed as max(chargeTimes) + k * sum(runningCosts), where max(chargeTimes) is the largest charge time in the selected subarray and sum(runningCosts) is the sum of their running costs. Determine the maximum number of consecutive robots that can operate without exceeding the budget.

Examples

Example 1

Input: chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25

Output: 3

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

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 Approach

Binary Search Over Answer Space

Use binary search on the possible number of consecutive robots. For each candidate length, check if any subarray of that length fits within the budget using an efficient sliding window and monotonic queue to track maximum charge times.

Sliding Window with Prefix Sums

Maintain a running sum of the selected subarray's running costs to calculate total cost efficiently. Update the window as you move through the array to avoid recomputation of sums for every subarray.

Monotonic Queue for Maximum Charge Time

Use a monotonic deque to track the maximum charge time in the current sliding window. This allows O(1) retrieval of the maximum charge when checking total cost for each candidate window.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to binary search over possible lengths combined with linear scan per candidate length using sliding window and monotonic queue. Space complexity is O(n) for the monotonic queue and prefix sums.

What Interviewers Usually Probe

Check if you can calculate subarray maximum efficiently instead of recomputing for every window.
Consider using binary search on the number of robots instead of iterating over all possible lengths.
Watch out for overflow when multiplying length by sum of running costs.

Common Pitfalls or Variants

Common pitfalls

Recomputing max(chargeTimes) for each subarray instead of using a monotonic queue.
Failing to handle edge cases where no robot can fit within the budget.
Using nested loops for every subarray length leading to TLE on large n.

Follow-up variants

Find maximum number of robots with arbitrary non-consecutive selection under budget constraints.
Calculate maximum robots for varying budgets given dynamic charge and running costs.
Minimize total cost for a fixed number of consecutive robots using similar sliding window approach.

FAQ

What is the main strategy to solve Maximum Number of Robots Within Budget?

The key strategy is binary search over possible consecutive robot counts combined with a sliding window and monotonic queue to track sums and maximum charges.

Can this problem be solved without binary search?

A brute-force approach is possible but inefficient; binary search over possible lengths drastically reduces time complexity.

Why do we use a monotonic queue in this problem?

The monotonic queue allows O(1) retrieval of the maximum charge time in the current window, which is crucial for calculating total cost efficiently.

What should I watch out for in edge cases?

Be careful when no consecutive robots fit the budget; the solution should correctly return 0 in such cases.

How does GhostInterview optimize solving this pattern?

It converts the problem into a checkable binary search over window lengths and highlights efficient data structures to maintain max and sums, preventing common TLE errors.

terminal

Solution

Solution 1: Two Pointers + Monotonic Queue

The problem is essentially finding the maximum value within a sliding window, which can be solved using a monotonic queue.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def maximumRobots(
        self, chargeTimes: List[int], runningCosts: List[int], budget: int
    ) -> int:
        q = deque()
        ans = s = l = 0
        for r, (t, c) in enumerate(zip(chargeTimes, runningCosts)):
            s += c
            while q and chargeTimes[q[-1]] <= t:
                q.pop()
            q.append(r)
            while q and (r - l + 1) * s + chargeTimes[q[0]] > budget:
                if q[0] == l:
                    q.popleft()
                s -= runningCosts[l]
                l += 1
            ans = max(ans, r - l + 1)
        return ans

Continue Practicing

#862 shortest subarray with sum at least k #2528 maximize the minimum powered city #1687 delivering boxes from storage to ports