Skip to main content
Talentd

Maximum Number of Robots Within Budget - Solution & Explanation

HardArrayBinary SearchQueueSliding Window14 min readAsked at: Amazon, Inmobi
Practice this problem

Problem Statement

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 == n
  • 1 <= n <= 5 * 104
  • 1 <= chargeTimes[i], runningCosts[i] <= 105
  • 1 <= 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.

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaC#

Java

C#

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with Monotonic DequeO(n)O(n)Best overall solution. Efficient when scanning the array once while maintaining the maximum charge time.
Binary Search with Prefix SumO(n log n)O(n)Useful when reasoning about window size feasibility or when applying binary search on the answer.

Video Solution

Leetcode 2398. Maximum Number of Robots Within Budget | Biweekly Contest 86. | Hard | Most Optimal • Code with Alisha • 3,621 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Number of Robots Within Budget with our built-in code editor and test cases.

Practice on FleetCode
Previous

Kth Smallest Product of Two Sorted Arrays

Next

Maximum Number of Tasks You Can Assign