Problem

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 thekrobots andsum(runningCosts)is the sum of running costs among thek` robots.

Return _themaximum number of consecutive robots you can run such that the total cost does not exceed _budget.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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 * 10^4
  • 1 <= chargeTimes[i], runningCosts[i] <= 10^5
  • 1 <= budget <= 1015

Solution

Method 1 – Sliding Window with Monotonic Queue

Intuition

We want the largest window of consecutive robots such that the cost formula max(chargeTimes) + k * sum(runningCosts) does not exceed the budget. To do this efficiently, we use a sliding window and a monotonic queue to keep track of the maximum charge time in the current window.

Approach

  1. Use two pointers (l, r) to represent the current window of robots.
  2. Maintain a monotonic queue to get the maximum charge time in the window in O(1) time.
  3. Maintain the sum of running costs in the window.
  4. For each r, expand the window and update the monotonic queue and running cost sum.
  5. If the total cost exceeds the budget, move l right, updating the queue and sum.
  6. Track the maximum window size that fits the budget.
  7. Return the maximum size found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        int n = chargeTimes.size(), ans = 0;
        deque<int> dq;
        long long sum = 0;
        for (int l = 0, r = 0; r < n; ++r) {
            sum += runningCosts[r];
            while (!dq.empty() && chargeTimes[dq.back()] <= chargeTimes[r]) dq.pop_back();
            dq.push_back(r);
            while (!dq.empty() && chargeTimes[dq.front()] + (r - l + 1) * sum > budget) {
                if (dq.front() == l) dq.pop_front();
                sum -= runningCosts[l++];
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func maximumRobots(chargeTimes []int, runningCosts []int, budget int64) int {
    n, ans := len(chargeTimes), 0
    dq := []int{}
    sum := int64(0)
    l := 0
    for r := 0; r < n; r++ {
        sum += int64(runningCosts[r])
        for len(dq) > 0 && chargeTimes[dq[len(dq)-1]] <= chargeTimes[r] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, r)
        for len(dq) > 0 && int64(chargeTimes[dq[0]])+int64(r-l+1)*sum > budget {
            if dq[0] == l {
                dq = dq[1:]
            }
            sum -= int64(runningCosts[l])
            l++
        }
        if r-l+1 > ans {
            ans = r - l + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = chargeTimes.length, ans = 0;
        Deque<Integer> dq = new ArrayDeque<>();
        long sum = 0;
        for (int l = 0, r = 0; r < n; r++) {
            sum += runningCosts[r];
            while (!dq.isEmpty() && chargeTimes[dq.peekLast()] <= chargeTimes[r]) dq.pollLast();
            dq.addLast(r);
            while (!dq.isEmpty() && chargeTimes[dq.peekFirst()] + (long)(r - l + 1) * sum > budget) {
                if (dq.peekFirst() == l) dq.pollFirst();
                sum -= runningCosts[l++];
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun maximumRobots(chargeTimes: IntArray, runningCosts: IntArray, budget: Long): Int {
        val n = chargeTimes.size
        var ans = 0
        val dq = ArrayDeque<Int>()
        var sum = 0L
        var l = 0
        for (r in 0 until n) {
            sum += runningCosts[r]
            while (dq.isNotEmpty() && chargeTimes[dq.last()] <= chargeTimes[r]) dq.removeLast()
            dq.addLast(r)
            while (dq.isNotEmpty() && chargeTimes[dq.first()] + (r - l + 1) * sum > budget) {
                if (dq.first() == l) dq.removeFirst()
                sum -= runningCosts[l++]
            }
            ans = maxOf(ans, r - l + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maximumRobots(self, chargeTimes: list[int], runningCosts: list[int], budget: int) -> int:
        from collections import deque
        n = len(chargeTimes)
        dq = deque()
        ans = 0
        s = 0
        l = 0
        for r in range(n):
            s += runningCosts[r]
            while dq and chargeTimes[dq[-1]] <= chargeTimes[r]:
                dq.pop()
            dq.append(r)
            while dq and chargeTimes[dq[0]] + (r - l + 1) * s > budget:
                if dq[0] == l:
                    dq.popleft()
                s -= runningCosts[l]
                l += 1
            ans = max(ans, r - l + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn maximum_robots(charge_times: Vec<i32>, running_costs: Vec<i32>, budget: i64) -> i32 {
        let n = charge_times.len();
        let mut dq = std::collections::VecDeque::new();
        let mut ans = 0;
        let mut sum = 0i64;
        let mut l = 0;
        for r in 0..n {
            sum += running_costs[r] as i64;
            while let Some(&idx) = dq.back() {
                if charge_times[idx] <= charge_times[r] { dq.pop_back(); } else { break; }
            }
            dq.push_back(r);
            while !dq.is_empty() && (charge_times[*dq.front().unwrap()] as i64 + (r as i64 - l as i64 + 1) * sum > budget) {
                if *dq.front().unwrap() == l { dq.pop_front(); }
                sum -= running_costs[l] as i64;
                l += 1;
            }
            ans = ans.max(r - l + 1);
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    maximumRobots(chargeTimes: number[], runningCosts: number[], budget: number): number {
        const n = chargeTimes.length;
        let ans = 0, sum = 0, l = 0;
        const dq: number[] = [];
        for (let r = 0; r < n; r++) {
            sum += runningCosts[r];
            while (dq.length && chargeTimes[dq[dq.length - 1]] <= chargeTimes[r]) dq.pop();
            dq.push(r);
            while (dq.length && chargeTimes[dq[0]] + (r - l + 1) * sum > budget) {
                if (dq[0] === l) dq.shift();
                sum -= runningCosts[l++];
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each robot is added and removed from the monotonic queue at most once, and the window slides linearly.
  • 🧺 Space complexity: O(n) — For the monotonic queue and prefix sums.