Maximum Number of Robots Within Budget

Hard
778.

Maximum Number of Robots Within Budget

Maximum Number of Robots Within Budget is a hard coding problem on arrays, two pointers and sliding window, asked in Amazon, Google and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} chargeTimes
 * @param {number[]} runningCosts
 * @param {number} budget
 * @return {number}
 */
var maximumRobots = function(chargeTimes, runningCosts, budget) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Robots Within Budget — Problem & Solution

Maximum Number of Robots Within Budget solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum Number of Robots Within Budget is a hard coding problem on arrays, two pointers and sliding window, asked in Amazon, Google and Flipkart interviews.

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

Hints for Maximum Number of Robots Within Budget

  1. Hint 1

    The cost of a window grows when the window grows, so the feasible windows form a sliding window.

  2. Hint 2

    The running-cost part is a prefix sum; the charge-time part is a window maximum.

  3. Hint 3

    A monotonic deque keeps the window maximum in amortised constant time.

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

  1. 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.
  2. Add runningCosts[r] to the running sum.
  3. 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.
  4. 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

Java

public static int maximumRobots(int[] chargeTimes, int[] runningCosts, int budget) {
    int n = chargeTimes.length;
    int[] dq = new int[n];
    int head = 0, tail = 0;
    long sum = 0;
    int l = 0, best = 0;
    for (int r = 0; r < n; r++) {
        while (tail > head && chargeTimes[dq[tail - 1]] <= chargeTimes[r]) tail--;
        dq[tail++] = r;
        sum += runningCosts[r];
        while (l <= r && chargeTimes[dq[head]] + (long) (r - l + 1) * sum > budget) {
            sum -= runningCosts[l];
            if (dq[head] == l) head++;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

C++

int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, int budget) {
    int n = (int) chargeTimes.size();
    deque<int> dq;
    long long sum = 0;
    int l = 0, best = 0;
    for (int r = 0; r < n; r++) {
        while (!dq.empty() && chargeTimes[dq.back()] <= chargeTimes[r]) dq.pop_back();
        dq.push_back(r);
        sum += runningCosts[r];
        while (l <= r && chargeTimes[dq.front()] + (long long) (r - l + 1) * sum > budget) {
            sum -= runningCosts[l];
            if (dq.front() == l) dq.pop_front();
            l++;
        }
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique