2398. Maximum Number of Robots Within Budget LeetCode Solution

In this guide, you will get 2398. Maximum Number of Robots Within Budget LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Robots Within Budget problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Number of Robots Within Budget solution in C++
Maximum Number of Robots Within Budget solution in Java
Maximum Number of Robots Within Budget solution in Python
Additional Resources

2398. Maximum Number of Robots Within Budget LeetCode Solution image

Problem Statement of Maximum Number of Robots Within Budget

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2398. Maximum Number of Robots Within Budget LeetCode Solution in C++

class Solution {
 public:
  int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts,
                    long long budget) {
    long cost = 0;
    deque<int> maxQ;  // Stores `chargeTimes[i]`.

    int j = 0;  // window's range := [i..j], so k = i - j + 1
    for (int i = 0; i < chargeTimes.size(); ++i) {
      cost += runningCosts[i];
      while (!maxQ.empty() && maxQ.back() < chargeTimes[i])
        maxQ.pop_back();
      maxQ.push_back(chargeTimes[i]);
      if (maxQ.front() + (i - j + 1) * cost > budget) {
        if (maxQ.front() == chargeTimes[j])
          maxQ.pop_front();
        cost -= runningCosts[j++];
      }
    }

    return chargeTimes.size() - j;
  }
};
/* code provided by PROGIEZ */

2398. Maximum Number of Robots Within Budget LeetCode Solution in Java

class Solution {
  public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
    long cost = 0;
    // Stores `chargeTimes[i]`.
    Deque<Integer> maxQ = new ArrayDeque<>();

    int j = 0; // window's range := [i..j], so k = i - j + 1
    for (int i = 0; i < chargeTimes.length; ++i) {
      cost += runningCosts[i];
      while (!maxQ.isEmpty() && maxQ.peekLast() < chargeTimes[i])
        maxQ.pollLast();
      maxQ.offerLast(chargeTimes[i]);
      if (maxQ.peekFirst() + (i - j + 1) * cost > budget) {
        if (maxQ.peekFirst() == chargeTimes[j])
          maxQ.pollFirst();
        cost -= runningCosts[j++];
      }
    }

    return chargeTimes.length - j;
  }
}
// code provided by PROGIEZ

2398. Maximum Number of Robots Within Budget LeetCode Solution in Python

class Solution:
  def maximumRobots(
      self,
      chargeTimes: list[int],
      runningCosts: list[int],
      budget: int,
  ) -> int:
    cost = 0
    maxQ = collections.deque()  # Stores `chargeTimes[i]`.

    j = 0  # window's range := [i..j], so k = i - j + 1
    for i, (chargeTime, runningCost) in enumerate(
            zip(chargeTimes, runningCosts)):
      cost += runningCost
      while maxQ and maxQ[-1] < chargeTime:
        maxQ.pop()
      maxQ.append(chargeTime)
      if maxQ[0] + (i - j + 1) * cost > budget:
        if maxQ[0] == chargeTimes[j]:
          maxQ.popleft()
        cost -= runningCosts[j]
        j += 1

    return len(chargeTimes) - j
 # code by PROGIEZ