2398. Maximum Number of Robots Within Budget
Problem Description
You are given n
robots, each with a specific time it takes to charge (chargeTimes[i]
) and a cost that it incurs when running (runningCosts[i]
). Your goal is to determine the maximum number of consecutive robots that can be active without exceeding a given budget. The total cost to run k
robots is calculated by adding the maximum charge time from the selected k
robots to the product of k
and the sum of their running costs.
The problem is essentially asking you to find the longest subsequence of robots that can operate concurrently within the constraints of your budget, taking into consideration both the upfront charge cost and the ongoing running costs.
Intuition
The solution utilizes the sliding window technique to find the longest subsequence of consecutive robots that can be run within the budget. To efficiently manage the running sum of the running costs and the maximum charge time within the current window, we can use a deque (double-ended queue) and maintain the sum of the running costs.
Sliding Window Technique
We iterate through the robots using a sliding window defined by two pointers, j
(the start) and i
(the end). For each position i
:
- A deque is used to keep track of the indices of the robots in the current window, maintaining the indices in decreasing order of their
chargeTimes
. - We add the robot at position
i
to the window. If it has a charge time greater than some robots already in the window, those robots are removed from the end of the deque because they are rendered irrelevant (a larger charge time has been found). - We add the running cost of the current robot to a running sum
s
. - We check if the current window exceeds the budget by calculating the total cost using the front of the deque (which has the robot with the maximum charge time) and the running sum
s
. If it does exceed the budget, we shrink the window from the left by increasingj
and adjusting the sum and deque accordingly. - The answer (
ans
) is updated as we go, to be the maximum window size found that satisfies the budget constraint.
By the end of the iteration, ans
holds the length of the longest subsequence of robots we can operate without exceeding the budget.
Learn more about Queue, Binary Search, Prefix Sum, Sliding Window and Heap (Priority Queue) patterns.
Solution Approach
The implementation uses a greedy approach combined with a sliding window technique to determine the maximum number of consecutive robots that can be run within the budget. Here's a step-by-step breakdown:
-
Initialization: A deque
q
is declared to keep track of the robots' indices in the window while ensuring access to the largestchargeTime
in constant time. Variables
is used to store the running sum ofrunningCosts
,j
is the start of the current window,ans
is the variable that will store the final result, andn
holds the length of the arrays. -
Sliding Window: This implementation uses a single loop that iterates over all robots' indices
i
from0
ton-1
. For each indexi
:- Insert the current robot into the deque:
- If there are robots in the deque with
chargeTimes
less than or equal to the current robot'schargeTime
, they are removed from the end since they do not affect the max anymore. - The current index
i
is added to the end of the deque.
- If there are robots in the deque with
- The running cost of the robot
i
is added to the running sums
.
- Insert the current robot into the deque:
-
Maintaining the Budget Constraint: The algorithm checks if the total cost of running robots from the current window exceeds the budget:
- While the sum of the maximum
chargeTime
(from the front of the deque) and the product ofs
and the window size (i - j + 1
) is greater thanbudget
, the window needs to be shrunk from the left. This includes:- If the robot at the start of the window is also at the front of the deque, it is removed.
- The running cost of the robot at
j
is subtracted froms
. - The start index
j
is incremented to shrink the window.
- While the sum of the maximum
-
Update the Result: After fixing the window by ensuring it's within the budget, update the maximum number of robots
ans
by comparing it with the size of the current window. -
Return the Result: After the loop finishes, the variable
ans
holds the length of the longest segment of consecutive robots that can be run without exceeding the budget, according to the specified cost function.
The algorithm's time complexity is O(n), where n is the number of robots, since each element is inserted and removed from the deque at most once. The usage of a deque enables the algorithm to determine the maximum chargeTime
in O(1) time while keeping the ability to insert and delete elements from both ends efficiently. The running sum s
is also updated in constant time, making this approach efficient for large inputs.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach.
Suppose we have n = 4
robots with the following chargeTimes
and runningCosts
:
chargeTimes = [3, 6, 1, 4] runningCosts = [2, 1, 3, 2]
And let's say our budget is 16
.
Now let's apply our sliding window technique:
-
Initialize our variable
s
to 0, our dequeq
to empty,ans
to 0, and our window startj
to 0. -
Start iterating with the sliding window:
i. Start with the first robot
i = 0
: -chargeTimes[i]
is 3; we add it to our dequeq
(which is now [0]). - We addrunningCosts[i]
tos
(which is now 2). - The window size isi - j + 1
which is1
at this point. - The total cost calculation ismax(chargeTimes)
(which is 3 from the deque) +s * window size
= 3 + 2 * 1 = 5, which is within the budget.ii. Move to the next robot
i = 1
: -chargeTimes[i]
is 6; since it's larger than the last element in the deque, we push it to the dequeq
(which is now [0,1]). - AddrunningCosts[i]
tos
(which is now 3). - The calculation now ismax(chargeTimes)
(which is 6) +s * window size
(2 * 2) = 6 + 4 = 10, still within the budget.iii. Move to robot
i = 2
: -chargeTimes[i]
is 1, it's less than the elements in the deque, so nothing is removed and it's added toq
(now [0,1,2]). - AddrunningCosts[i]
tos
(which is now 6). - The total cost ismax(chargeTimes)
(which is still 6) +s * window size
(3 * 3) = 6 + 9 = 15, within the budget.iv. Move to robot
i = 3
: -chargeTimes[i]
is 4, which is less than 6 but more than 3, so we pop from the end of the deque until the condition is satisfied and then add index 3. Deque q is now [0,1,3]. - AddrunningCosts[i]
tos
(which is now 8). - The total cost now ismax(chargeTimes)
(which is still 6) +s * window size
(4 * 4) = 6 + 16 = 22, which exceeds the budget. -
To maintain the budget constraint:
i. When the cost exceeds the budget (which is the case now), we need to shrink our window from the left: - Since
j = 0
is at the front of the deque, remove it from the dequeq
(now [1,3]). - SubtractrunningCosts[j]
froms
to update the running sum (now 6). - Incrementj
to 1 to shrink the window. - Now, the window size is 3 (from index 1 to 3), and the cost calculation ismax(chargeTimes)
(which is 6) +s * window size
= 6 + 6 * 3 = 24, still over budget.ii. Repeat the process by incrementing
j
to 2 and adjust:q
(now [3]),s
to 3, andans
remains 2 which was the biggest window size that was in budget before.iii. The current window size is now
i - j + 1
which is 2, and the total cost ismax(chargeTimes)
(which is 4) +s * window size
= 4 + 3 * 2 = 10, within the budget. - We updateans
to the current window size, but since it's not bigger than the previousans
(which was 2),ans
remains 2. -
After iterating through all robots, our answer
ans
is2
which indicates we can run at most 2 consecutive robots within the given budget.
By following this approach, we manage to calculate the maximum number of consecutive robots that can be active within the allocated budget in an efficient manner, with a loop that runs linearly relative to the number of robots.
Solution Implementation
1from collections import deque
2
3class Solution:
4 def maximum_robots(self, charge_times, running_costs, budget):
5 # Deque to store indices of robots with charge_times in non-increasing order
6 max_charge_deque = deque()
7 # Holds the sum of the running costs of the current set of robots
8 running_cost_sum = 0
9 # Stores the maximum number of robots that can be activated
10 max_robots = 0
11 # Starting index of the current window of robots
12 start_idx = 0
13
14 # Iterate over all the robots
15 for i in range(len(charge_times)):
16 current_charge = charge_times[i]
17 current_running_cost = running_costs[i]
18
19 # Remove robots from the back of the deque if their charge time is less than
20 # or equal to the current robot's charge time
21 while max_charge_deque and charge_times[max_charge_deque[-1]] <= current_charge:
22 max_charge_deque.pop()
23 # Add the current robot's index to the deque
24 max_charge_deque.append(i)
25
26 # Add the current robot's running cost to the sum
27 running_cost_sum += current_running_cost
28
29 # Ensure the sum of the max charge time in the window and the total running cost
30 # for the robots in the window does not exceed the budget
31 while (max_charge_deque and
32 charge_times[max_charge_deque[0]] + (i - start_idx + 1) * running_cost_sum > budget):
33 # If the robot at the front of the deque is the robot at start_idx, remove it
34 if max_charge_deque[0] == start_idx:
35 max_charge_deque.popleft()
36 # Remove the robot's running cost at start_idx from the sum and move start_idx forward
37 running_cost_sum -= running_costs[start_idx]
38 start_idx += 1
39
40 # Update the maximum number of robots that can be activated
41 max_robots = max(max_robots, i - start_idx + 1)
42
43 return max_robots
44
1class Solution {
2
3 // Method to calculate the maximum number of robots that can be activated within the budget
4 public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
5 // Queue to store indices of robots to ensure chargeTimes are in non-increasing order from front to back
6 Deque<Integer> queue = new ArrayDeque<>();
7
8 // Total number of robots
9 int numOfRobots = chargeTimes.length;
10
11 // Running sum of the costs
12 long runningSum = 0;
13
14 // Starting index for the current window
15 int windowStart = 0;
16
17 // Result, i.e., the maximum number of robots that can be activated
18 int maxRobots = 0;
19
20 // Loop over each robot
21 for (int i = 0; i < numOfRobots; ++i) {
22 // Current robot's charge time and running cost
23 int currentChargeTime = chargeTimes[i];
24 int currentRunningCost = runningCosts[i];
25
26 // Remove robots from the back of the queue whose charge time is less than or equal to the current one
27 while (!queue.isEmpty() && chargeTimes[queue.getLast()] <= currentChargeTime) {
28 queue.pollLast();
29 }
30
31 // Add the current robot to the queue
32 queue.offer(i);
33
34 // Update the running sum with the current robot's running cost
35 runningSum += currentRunningCost;
36
37 // If the total cost exceeds the budget, remove robots from the front of the queue
38 while (!queue.isEmpty() && chargeTimes[queue.getFirst()] + (i - windowStart + 1) * runningSum > budget) {
39 if (queue.getFirst() == windowStart) {
40 queue.pollFirst(); // Remove the robot at the start of the window if it is at the front of the queue
41 }
42 runningSum -= runningCosts[windowStart++]; // Reduce the running sum and move the window start forward
43 }
44
45 // Update the result with the maximum number of robots
46 maxRobots = Math.max(maxRobots, i - windowStart + 1);
47 }
48
49 // Return the maximum number of robots
50 return maxRobots;
51 }
52}
53
1#include <vector>
2#include <deque>
3using std::vector;
4using std::deque;
5using std::max;
6
7class Solution {
8public:
9 // Finds the maximum number of robots that can be activated within a given budget
10 int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
11 // Deque to store indices of robots with chargeTimes in non-increasing order
12 deque<int> maxChargeDeque;
13 // Holds the sum of the running costs of the current set of robots
14 long long runningCostSum = 0;
15 // Stores the maximum number of robots that can be activated
16 int maxRobots = 0;
17 // Starting index of the current window of robots
18 int startIdx = 0;
19 int numRobots = chargeTimes.size();
20
21 // Iterate over all the robots
22 for (int i = 0; i < numRobots; ++i) {
23 int currentCharge = chargeTimes[i];
24 int currentRunningCost = runningCosts[i];
25
26 // Remove robots from the back of the deque if their charge time is less than
27 // or equal to the current robot's charge time
28 while (!maxChargeDeque.empty() && chargeTimes[maxChargeDeque.back()] <= currentCharge) {
29 maxChargeDeque.pop_back();
30 }
31 // Add the current robot's index to the deque
32 maxChargeDeque.push_back(i);
33
34 // Add the current robot's running cost to the sum
35 runningCostSum += currentRunningCost;
36
37 // Ensure the sum of the max charge time in the window and the total running cost
38 // for the robots in the window does not exceed the budget
39 while (!maxChargeDeque.empty() && chargeTimes[maxChargeDeque.front()] + (i - startIdx + 1) * runningCostSum > budget) {
40 // If the robot at the front of the deque is the robot at the startIdx, remove it
41 if (maxChargeDeque.front() == startIdx) {
42 maxChargeDeque.pop_front();
43 }
44 // Remove the robot's running cost at startIdx from the sum and move the startIdx forward
45 runningCostSum -= runningCosts[startIdx++];
46 }
47
48 // Update the maximum number of robots that can be activated
49 maxRobots = max(maxRobots, i - startIdx + 1);
50 }
51
52 return maxRobots;
53 }
54};
55
1function maximumRobots(chargeTimes: number[], runningCosts: number[], budget: number): number {
2 // Deque to store indices of robots with chargeTimes in non-increasing order
3 const maxChargeDeque: number[] = [];
4 // Holds the sum of the running costs of the current set of robots
5 let runningCostSum = 0;
6 // Stores the maximum number of robots that can be activated
7 let maxRobots = 0;
8 // Starting index of the current window of robots
9 let startIdx = 0;
10 const numRobots = chargeTimes.length;
11
12 // Iterate over all the robots
13 for (let i = 0; i < numRobots; ++i) {
14 const currentCharge = chargeTimes[i];
15 const currentRunningCost = runningCosts[i];
16
17 // Remove robots from the back of the deque if their charge time is less than
18 // or equal to the current robot's charge time
19 while (maxChargeDeque.length > 0 && chargeTimes[maxChargeDeque[maxChargeDeque.length - 1]] <= currentCharge) {
20 maxChargeDeque.pop();
21 }
22 // Add the current robot's index to the deque
23 maxChargeDeque.push(i);
24
25 // Add the current robot's running cost to the sum
26 runningCostSum += currentRunningCost;
27
28 // Ensure the sum of the max charge time in the window and the total running cost
29 // for the robots in the window does not exceed the budget
30 while (maxChargeDeque.length > 0 && chargeTimes[maxChargeDeque[0]] + (i - startIdx + 1) * runningCostSum > budget) {
31 // If the robot at the front of the deque is the robot at startIdx, remove it
32 if (maxChargeDeque[0] === startIdx) {
33 maxChargeDeque.shift();
34 }
35 // Remove the robot's running cost at startIdx from the sum and move the startIdx forward
36 runningCostSum -= runningCosts[startIdx++];
37 }
38
39 // Update the maximum number of robots that can be activated
40 maxRobots = Math.max(maxRobots, i - startIdx + 1);
41 }
42
43 return maxRobots;
44}
45
Time and Space Complexity
Time Complexity
The given code maintains a deque (q
) and iterates over the chargeTimes
array once. The primary operations within the loop are:
-
Adding elements to the deque which takes
O(1)
time per operation, but elements are only added when they are larger than the last element. Since elements are removed from the deque if they are not greater, each element is added and removed at most once. -
Removing elements from the dequeue from both ends also takes
O(1)
time per operation, ensuring that no element is processed more than once. -
The while loop inside the for loop is executed to ensure that the current maximum charge time and total cost do not exceed the budget. Although it seems nested, it does not make the overall algorithm exceed
O(n)
because each element is added to the deque only once, and hence can be removed only once.
Given these observations, each operation is in constant time regarding the current index, and since we only iterate over the array once, the time complexity is O(n)
where n
is the length of the chargeTimes
array.
Space Complexity
The space complexity is primarily determined by the deque q
, which in the worst case might hold all elements if the chargeTimes
are in non-decreasing order. Thus, in the worst-case scenario, the space complexity is O(n)
where n
is the length of the chargeTimes
array.
Other variables used (such as s
, j
, a
, b
, and ans
) only require constant space (O(1)
), so do not affect the overall space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Want a Structured Path to Master System Design Too? Donāt Miss This!