Maximum Number of Robots Within Budget — Hard Problem & Solution

You run a consecutive stretch of robots. Running robots i … j costs max(chargeTimes[i…j]) + (j - i + 1) · sum(runningCosts[i…j]) Return the maximum number…

Difficulty: Hard
Topics: Arrays, Two Pointers, Sliding Window, Queue, Monotonic Queue
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You run a consecutive stretch of robots. Running robots i … j costs

max(chargeTimes[i…j]) + (j - i + 1) · sum(runningCosts[i…j])

Return the maximum number of consecutive robots you can run without exceeding budget.

Example 1

Input: chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
Output: 3
Explanation: Robots 0–2 cost 6 + 3 · 6 = 24.

Example 2

Input: chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
Output: 0
Explanation: Even one robot is too expensive.

Example 3

Input: chargeTimes = [1,1,1], runningCosts = [1,1,1], budget = 100
Output: 3

Constraints

1 <= chargeTimes.length == runningCosts.length <= 1000
1 <= chargeTimes[i], runningCosts[i] <= 100000
1 <= budget <= 1000000000

How to solve Maximum Number of Robots Within Budget

Extend the window to the right and shrink from the left whenever the cost exceeds the budget. The only awkward term is the window maximum of chargeTimes, which a decreasing deque of indices maintains as the window slides.

Approach

For each right end r, pop the deque's back while its charge time is at most chargeTimes[r], then push r; the front is now the window maximum.
Add runningCosts[r] to the running sum.
While the window's cost exceeds the budget, drop the left element from the sum and, if it was the deque's front, from the deque.
Track the largest window seen.

Why it works

Both the maximum and the length-times-sum term are non-decreasing as the window grows, so for each r the feasible left ends form a suffix — a genuine sliding window, with l never moving backwards. The deque stays decreasing, so its front is always the maximum of the current window, and each index enters and leaves once.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

(j - i + 1) · sum reaches about 10^3 · 10^3 · 10^5 = 10^11, so the cost must be computed in 64-bit even though the answer is small.
Popping the deque with < instead of <= leaves stale equal maxima behind — harmless for the value but it must still be removed when it falls out of the window.
The answer can be 0 when no single robot fits.

Reference solution

Python

from collections import deque
from typing import List

def maximumRobots(chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
    dq = deque()
    total = 0
    l = 0
    best = 0
    for r in range(len(chargeTimes)):
        while dq and chargeTimes[dq[-1]] <= chargeTimes[r]:
            dq.pop()
        dq.append(r)
        total += runningCosts[r]
        while l <= r and chargeTimes[dq[0]] + (r - l + 1) * total > budget:
            total -= runningCosts[l]
            if dq[0] == l:
                dq.popleft()
            l += 1
        best = max(best, r - l + 1)
    return best

JavaScript

var maximumRobots = function(chargeTimes, runningCosts, budget) {
    var n = chargeTimes.length;
    var dq = [];
    var head = 0, sum = 0, l = 0, best = 0;
    for (var r = 0; r < n; r++) {
        while (dq.length > head && chargeTimes[dq[dq.length - 1]] <= chargeTimes[r]) dq.pop();
        dq.push(r);
        sum += runningCosts[r];
        while (l <= r && chargeTimes[dq[head]] + (r - l + 1) * sum > budget) {
            sum -= runningCosts[l];
            if (dq[head] === l) head++;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue