Maximum Number of Robots Within Budget solution and explanation
9 more videos on this problem
Leetcode 2398. Maximum Number of Robots Within Budget | Biweekly Contest 86. | Hard | Most OptimalCode with Alisha · 38:45 · 3K views
2398. Maximum Number of Robots Within Budget | Biweekly Contest 86 | LeetCode 2398Bro Coders · 12:51 · 2K views
Biweekly Contest 86 | 6143. Maximum Number of Robots Within BudgetcodingMohan · 23:00 · 1K views
2398. Maximum Number of Robots Within Budget | Leetcode Biweekly Contest 86 | BINARY SEARCHcode Explainer · 15:14 · 749 views
Maximum Number of Robots Within Budget - Leetcode Biweekly Contest 86Gopala Krishna Reddy Maguluri · 0:29 · 715 views
2398. Maximum Number of Robots Within Budget (Leetcode Hard)Programming Live with Larry · 24:36 · 641 views
【每日一题】LeetCode 2398. Maximum Number of Robots Within BudgetHuifeng Guan · 23:15 · 438 views
Leetcode 2398. Maximum Number of Robots Within BudgetAlgorithms Casts · 23:10 · 316 views
Leetcode 2398. Maximum Number of Robots Within Budget (monotonic queue)LetsCode · 9:39 · 189 views
Leetcode 2398-s2. Maximum Number of Robots Within Budget-two-pointer sliding window, monotonic stackCode-Yao · 13:32 · 157 views
The 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 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 == n1 <= n <= 5 * 1041 <= chargeTimes[i], runningCosts[i] <= 1051 <= budget <= 1015
Approach overview
Problem Overview: You are given two arrays representing robot chargeTimes and runningCosts. Running k robots costs max(chargeTimes in window) + k * sum(runningCosts in window). The task is to find the largest group of consecutive robots that can run without exceeding the given budget.
Approach 1: Sliding Window with Monotonic Deque (O(n) time, O(n) space)
This is the optimal solution and relies on a sliding window combined with a monotonic queue. Expand the right pointer to include more robots while maintaining the sum of runningCosts. A deque keeps indices of robots in decreasing order of chargeTimes, so the front always holds the maximum charge time in the current window. Each time the window grows, compute the cost using maxCharge + windowSize * runningCostSum. If the cost exceeds the budget, move the left pointer forward and update the structures. Every element enters and leaves the deque at most once, giving linear time complexity. This approach works well because it efficiently tracks the maximum value while dynamically adjusting the window.
Approach 2: Binary Search with Prefix Sum (O(n log n) time, O(n) space)
This approach searches for the maximum valid window size using binary search. For a candidate size k, check if any subarray of length k satisfies the budget constraint. A prefix sum array allows constant-time computation of the sum of runningCosts for any window. To evaluate the maximum chargeTimes within each window, maintain a deque that stores indices in decreasing order, similar to the sliding window maximum technique. If at least one window of size k meets the budget condition, increase the search range; otherwise decrease it. Binary search narrows down the largest feasible window length.
Recommended for interviews: Interviewers typically expect the sliding window + monotonic deque solution. It demonstrates strong understanding of window expansion, maintaining dynamic maximum values, and amortized O(n) processing. The binary search approach is also valid and easier to reason about for some candidates, but the linear-time sliding window solution shows deeper algorithmic skill.
Approach 1: Approach 1: Sliding Window with Deque for Maximum
This approach involves using a sliding window technique along with a deque to maintain the maximum charge time within the current window. The goal is to efficiently manage the constraints such as recalculating the maximum value without iterating over the entire window each time.
We slide a window (i.e., a contiguous subarray) over the robots. The window expands by including a new robot, and contracts when the budget constraint is violated. Within this window, the max function and the sum function are used to compute the total cost. The sliding window and deque help manage the max charge time efficiently by allowing for constant-time insertion and removal of the charge times.
from collections import deque
def max_robots(chargeTimes, runningCosts, budget):
n = len(chargeTimes)
left = 0
total_running_cost = 0
deq = deque()
max_robots = 0
for right in range(n):
# Add the new element to the running cost
total_running_cost += runningCosts[right]
# Maintain the deque for maximum charge time
while deq and chargeTimes[deq[-1]] <= chargeTimes[right]:
deq.pop()
deq.append(right)
# Calculate the total cost for current window
while deq and (chargeTimes[deq[0]] + (right - left + 1) * total_running_cost) > budget:
if deq[0] == left:
deq.popleft()
total_running_cost -= runningCosts[left]
left += 1
# Update maximum number of robots
max_robots = max(max_robots, right - left + 1)
return max_robots
# Example usage
chargeTimes = [3, 6, 1, 3, 4]
runningCosts = [2, 1, 3, 4, 5]
budget = 25
print(max_robots(chargeTimes, runningCosts, budget)) # Output: 3#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int maxRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
int n = chargeTimes.size();
deque<int> deq;
int left = 0;
long long total_running_cost = 0;
int max_robots = 0;
for (int right = 0; right < n; ++right) {
total_running_cost += runningCosts[right];
while (!deq.empty() && chargeTimes[deq.back()] <= chargeTimes[right]) {
deq.pop_back();
}
deq.push_back(right);
while (!deq.empty() && (chargeTimes[deq.front()] + (right - left + 1) * total_running_cost) > budget) {
if (deq.front() == left) deq.pop_front();
total_running_cost -= runningCosts[left];
left++;
}
max_robots = max(max_robots, right - left + 1);
}
return max_robots;
}
int main() {
vector<int> chargeTimes = {3, 6, 1, 3, 4};
vector<int> runningCosts = {2, 1, 3, 4, 5};
long long budget = 25;
cout << maxRobots(chargeTimes, runningCosts, budget) << endl; // Output: 3
return 0;
}This Python function uses a deque to track the indices of chargeTimes for which we need to calculate the maximum effectively within a sliding window. The window's total running cost and the maximum charge time (determined by deque) are used to confirm whether the current set of robots fits within the given budget.
The time complexity is O(n) because each element is processed at most twice by deque operations (once when added, once when removed). The space complexity is O(k) where k is the maximum number of elements that can fit in the deque, which is bounded by the number of robots.
Approach 2: Approach 2: Binary Search with Prefix Sum
This approach uses binary search to find the maximum size of subarrays where the cost does not exceed the budget. The idea is to use a combination of binary search and prefix sums to evaluate whether it's possible to run a specific number of robots simultaneously without exceeding the budget. For each midpoint in the binary search, you need to check possible windows using prefix sum calculations.
import java.util.*;
public class MaxRobots {
public static int maxRobots(int[] chargeTimes, int[] runningCosts, long budget) {
int n = chargeTimes.length;
long[] runningCostPrefix = new long[n + 1];
for (int i = 0; i < n; i++) {
runningCostPrefix[i + 1] = runningCostPrefix[i] + runningCosts[i];
}
int left = 0, right = n, result = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (canRunRobots(chargeTimes, runningCostPrefix, mid, budget)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
private static boolean canRunRobots(int[] chargeTimes, long[] runningCostPrefix, int k, long budget) {
Deque<Integer> deq = new ArrayDeque<>();
for (int i = 0; i < chargeTimes.length; i++) {
if (i >= k) {
if (deq.peekFirst() == i - k) {
deq.pollFirst();
}
}
while (!deq.isEmpty() && chargeTimes[deq.peekLast()] <= chargeTimes[i]) {
deq.pollLast();
}
deq.addLast(i);
if (i >= k - 1) {
long totalCost = chargeTimes[deq.peekFirst()] +
k * (runningCostPrefix[i + 1] - runningCostPrefix[i + 1 - k]);
if (totalCost <= budget) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
int[] chargeTimes = {3, 6, 1, 3, 4};
int[] runningCosts = {2, 1, 3, 4, 5};
int budget = 25;
System.out.println(maxRobots(chargeTimes, runningCosts, budget)); // Output: 3
}
}using System;
using System.Collections.Generic;
class MaxRobots {
public static int MaxRobots(int[] chargeTimes, int[] runningCosts, long budget) {
int n = chargeTimes.Length;
long[] runningCostPrefix = new long[n + 1];
for (int i = 0; i < n; i++) {
runningCostPrefix[i + 1] = runningCostPrefix[i] + runningCosts[i];
}
int left = 0, right = n, result = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (CanRunRobots(chargeTimes, runningCostPrefix, mid, budget)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
private static bool CanRunRobots(int[] chargeTimes, long[] runningCostPrefix, int k, long budget) {
LinkedList<int> deq = new LinkedList<int>();
for (int i = 0; i < chargeTimes.Length; i++) {
if (i >= k) {
if (deq.First.Value == i - k) deq.RemoveFirst();
}
while (deq.Count > 0 && chargeTimes[deq.Last.Value] <= chargeTimes[i]) {
deq.RemoveLast();
}
deq.AddLast(i);
if (i >= k - 1) {
long totalCost = chargeTimes[deq.First.Value] + k * (runningCostPrefix[i + 1] - runningCostPrefix[i + 1 - k]);
if (totalCost <= budget) {
return true;
}
}
}
return false;
}
public static void Main() {
int[] chargeTimes = { 3, 6, 1, 3, 4 };
int[] runningCosts = { 2, 1, 3, 4, 5 };
long budget = 25;
Console.WriteLine(MaxRobots(chargeTimes, runningCosts, budget)); // Output: 3
}
}This Java solution applies a combination of binary search to find the maximum number of robots and uses deque within a helper function to manage the sliding window size of robots we are evaluating.
The binary search part has a time complexity of O(log n), and for each mid calculation, the cost checks take O(n), leading to a total complexity of O(n log n). The space complexity is O(n) due to the use of the runningCostsPrefix array and deque.
Approach 3: Two Pointers + Monotonic Queue
The problem is essentially finding the maximum value within a sliding window, which can be solved using a monotonic queue.
We only need to use binary search to enumerate the size of the window k, and find the largest k that satisfies the problem requirements.
In the implementation process, we don't actually need to perform binary search enumeration. We just need to change the fixed window to a non-fixed window with double pointers.
The time complexity is O(n), and the space complexity is O(n), where n is the number of robots in the problem.
function maximumRobots(chargeTimes: number[], runningCosts: number[], budget: number): number {
const q = new Deque<number>();
const n = chargeTimes.length;
let [ans, s] = [0, 0];
for (let l = 0, r = 0; r < n; ++r) {
s += runningCosts[r];
while (!q.isEmpty() && chargeTimes[q.backValue()!] <= chargeTimes[r]) {
q.popBack();
}
q.pushBack(r);
while (!q.isEmpty() && (r - l + 1) * s + chargeTimes[q.frontValue()!] > budget) {
if (q.frontValue() === l) {
q.popFront();
}
s -= runningCosts[l++];
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
class Node<T> {
value: T;
next: Node<T> | null;
prev: Node<T> | null;
constructor(value: T) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class Deque<T> {
private front: Node<T> | null;
private back: Node<T> | null;
private size: number;
constructor() {
this.front = null;
this.back = null;
this.size = 0;
}
pushFront(val: T): void {
const newNode = new Node(val);
if (this.isEmpty()) {
this.front = newNode;
this.back = newNode;
} else {
newNode.next = this.front;
this.front!.prev = newNode;
this.front = newNode;
}
this.size++;
}
pushBack(val: T): void {
const newNode = new Node(val);
if (this.isEmpty()) {
this.front = newNode;
this.back = newNode;
} else {
newNode.prev = this.back;
this.back!.next = newNode;
this.back = newNode;
}
this.size++;
}
popFront(): T | undefined {
if (this.isEmpty()) {
return undefined;
}
const value = this.front!.value;
this.front = this.front!.next;
if (this.front !== null) {
this.front.prev = null;
} else {
this.back = null;
}
this.size--;
return value;
}
popBack(): T | undefined {
if (this.isEmpty()) {
return undefined;
}
const value = this.back!.value;
this.back = this.back!.prev;
if (this.back !== null) {
this.back.next = null;
} else {
this.front = null;
}
this.size--;
return value;
}
frontValue(): T | undefined {
return this.front?.value;
}
backValue(): T | undefined {
return this.back?.value;
}
getSize(): number {
return this.size;
}
isEmpty(): boolean {
return this.size === 0;
}
}func maximumRobots(chargeTimes []int, runningCosts []int, budget int64) (ans int) {
q := Deque{}
s := int64(0)
l := 0
for r, t := range chargeTimes {
s += int64(runningCosts[r])
for !q.Empty() && chargeTimes[q.Back()] <= t {
q.PopBack()
}
q.PushBack(r)
for !q.Empty() && int64(r-l+1)*s+int64(chargeTimes[q.Front()]) > budget {
if q.Front() == l {
q.PopFront()
}
s -= int64(runningCosts[l])
l++
}
ans = max(ans, r-l+1)
}
return
}
// template
type Deque struct{ l, r []int }
func (q Deque) Empty() bool {
return len(q.l) == 0 && len(q.r) == 0
}
func (q Deque) Size() int {
return len(q.l) + len(q.r)
}
func (q *Deque) PushFront(v int) {
q.l = append(q.l, v)
}
func (q *Deque) PushBack(v int) {
q.r = append(q.r, v)
}
func (q *Deque) PopFront() (v int) {
if len(q.l) > 0 {
q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
} else {
v, q.r = q.r[0], q.r[1:]
}
return
}
func (q *Deque) PopBack() (v int) {
if len(q.r) > 0 {
q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
} else {
v, q.l = q.l[0], q.l[1:]
}
return
}
func (q Deque) Front() int {
if len(q.l) > 0 {
return q.l[len(q.l)-1]
}
return q.r[0]
}
func (q Deque) Back() int {
if len(q.r) > 0 {
return q.r[len(q.r)-1]
}
return q.l[0]
}
func (q Deque) Get(i int) int {
if i < len(q.l) {
return q.l[len(q.l)-1-i]
}
return q.r[i-len(q.l)]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sliding Window with Deque for Maximum | The time complexity is O(n) because each element is processed at most twice by deque operations (once when added, once when removed). The space complexity is O(k) where k is the maximum number of elements that can fit in the deque, which is bounded by the number of robots. |
| Approach 2: Binary Search with Prefix Sum | The binary search part has a time complexity of O(log n), and for each mid calculation, the cost checks take O(n), leading to a total complexity of O(n log n). The space complexity is O(n) due to the use of the runningCostsPrefix array and deque. |
| Two Pointers + Monotonic Queue | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Monotonic Deque | O(n) | O(n) | Best overall solution. Efficient when scanning the array once while maintaining the maximum charge time. |
| Binary Search with Prefix Sum | O(n log n) | O(n) | Useful when reasoning about window size feasibility or when applying binary search on the answer. |
Frequently asked questions
Is Maximum Number of Robots Within Budget easy or hard?
Maximum Number of Robots Within Budget is classified as a Hard problem on LeetCode. The difficulty comes from combining multiple techniques—sliding window, monotonic queue, and cost calculation—into one efficient O(n) solution.
Maximum Number of Robots Within Budget Python/Java solution
Python solutions typically use collections.deque to maintain the monotonic queue and a sliding window for O(n) processing. Java implementations often use ArrayDeque for the same purpose. Both versions maintain the maximum charge time and a running sum of costs to enforce the budget constraint.
How to solve Maximum Number of Robots Within Budget in O(n)?
Use a sliding window with two pointers and maintain the maximum charge time using a monotonic deque. Keep a running sum of runningCosts for the current window. Expand the window to the right, and when the total cost exceeds the budget, move the left pointer until the constraint is satisfied again.
What is the best approach for Maximum Number of Robots Within Budget?
The most efficient approach uses a sliding window with a monotonic deque. The deque maintains the maximum charge time inside the window while a running sum tracks running costs. This allows checking the cost formula in constant time while expanding and shrinking the window, giving an overall O(n) time complexity.
Is Maximum Number of Robots Within Budget asked at Google/Amazon/Meta?
Problems combining sliding window and monotonic queue patterns frequently appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests understanding of dynamic window constraints and maintaining maximum values efficiently.
What data structure is used in Maximum Number of Robots Within Budget?
The key data structure is a monotonic deque (monotonic queue) that stores indices of robots in decreasing order of chargeTimes. This allows constant-time access to the maximum charge time in the current window while supporting efficient insertions and removals during window adjustments.
What is the time complexity of Maximum Number of Robots Within Budget?
The optimal sliding window solution runs in O(n) time because each robot index is added and removed from the deque at most once. The binary search alternative runs in O(n log n) since it checks feasibility for different window sizes. Both approaches require O(n) additional space.