2398. Max Robots

Maximum Number of Robots Within Budget

Problem 2398 hovers around a 38% acceptance rate, yet it really just tests whether we know one fundamental skill: reading the problem carefully.

Once we do, we'll be confident that monotonic deque + sliding window + prefix sum trio can take it down together.

chargeTimes and runningCosts Are Always Natural Numbers

Our input has two arrays: chargeTimes and runningCosts, both of length $n$.

Index $i$ holds the charge time and running cost of $i^{\text{th}}$ robot, respectively.

Both are natural numbers — makes sense: a negative running cost would mean

suppliers are paying factories to take materials. Would you trust robots made like that?

Same for charge time — a negative value would mean the universe has collapsed, right?

Our third input is a positive integer budget. The cost formula for running $k$ selected robots is:

Total cost = max charge time among $k$ robots + $k$ × sum of all $k$ robots' running costs

The question is: under budget, what's the maximum number of consecutive robots that can run simultaneously?

Note the word consecutive — we can't pick robot $i$ and robot $i + 2$ while skipping robot $i + 1$.

With this in mind, we notice a key insight: for $0 \leq i \leq j \leq l < n$,

once total cost of robots $i$ through $j$ exceeds budget, robots $i$ through $l$ will also exceed budget by an even wider margin. Why?

max(chargeTimes[i:j + 1]) $\leq$ max(chargeTimes[i:l + 1]). The former is a subset of the latter.

The "max charge time among $k$ robots" in this formula can only increase.

And since running costs are natural numbers, sum(runningCosts[i:l + 1]) > sum(runningCosts[i:j + 1]).

$k$ only grows as more robots are added. All three components can't decrease, so neither can the total cost.

Conclusion: once robots $i$ through $j$ exceed budget, robot $i$ must be dropped to have any chance of getting back under budget.

This is monotonicity: invalidated robots never become valid again.

Just keep scanning forward. No need to look back. We smell $O(n)$ solution within reach.

Although suitable data structures are required to realize monotonicity in $O(n)$.

Three Data Structures

1. Sliding Window: Define Search Range

From the above, we establish two pointers: startIdx and endIdx,

representing robots at startIdx through endIdx — a total of endIdx + 1 - startIdx robots under evaluation.

Once total cost exceeds budget, increment startIdx until cost is back within budget, or startIdx > endIdx.

2. Monotonic Deque: Max Charge Time in Window

When incrementing endIdx, we need the max charge time among robots at startIdx to endIdx.

Get a monotonic decreasing deque to track it. Compare robot endIdx's charge time against deque's tail:

while tail's charge time $\leq$ charge time of robot at endIdx, tail is irrelevant. Pop it.

Stop when deque is empty or tail's charge time > charge time of robot at endIdx.

Also, when startIdx increases, check if deque's front index has fallen out of window. If so, pop it.

Remaining members naturally shift up, updating window's max charge time.

3. Prefix Sum: Total Running Cost in Window

Maintain a variable windowTotalCost for total running cost of robots at startIdx to endIdx.

When incrementing endIdx: add running cost of robot at endIdx to windowTotalCost.

When incrementing startIdx: subtract running cost of robot at startIdx from windowTotalCost.

This ensures an accurate window running cost at any moment.

Once startIdx stops rising, all robots in window won't exceed budget.

Robot count is endIdx + 1 - startIdx (1).

As designed, startIdx may keep incrementing until startIdx > endIdx.

For each endIdx, startIdx can reach at most endIdx + 1. But that's OK,

because count formula in (1) gives endIdx + 1 - startIdx = 0, meaning no robots are selected. A valid outcome.

Now we just simply compare with respect to historical maximum and return it at the end~~

It really comes down to reading constraints carefully, then figuring out which structures best preserve correctness under those constraints. Both time and space: $O(n)$.

C++

#include <queue>
#include <vector>
using namespace std;

int countMaxRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) // LeetCode Q.2398.
{
    int maxRobotsCount = 0; // Base case.

    long long windowTotalCost = 0;

    int startIdx = 0;
    deque<pair<int, int>> queue; // Format: {charge time, idx}.

    for (int endIdx = 0; endIdx < chargeTimes.size(); endIdx++) {
        windowTotalCost += runningCosts[endIdx];

        while (!queue.empty() && queue.back().first <= chargeTimes[endIdx])
            queue.pop_back();

        queue.push_back({chargeTimes[endIdx], endIdx});

        int robotsCount = endIdx + 1 - startIdx;
        int maxChargeTime = queue.front().first;

        while (budget < maxChargeTime + robotsCount * windowTotalCost) {
            windowTotalCost -= runningCosts[startIdx];

            startIdx++;
            robotsCount--;

            if (!queue.empty() && queue.front().second < startIdx)
                queue.pop_front();

            if (startIdx > endIdx)
                break; // 0 robots at hand.
        }

        if (robotsCount > maxRobotsCount)
            maxRobotsCount = robotsCount;
    }

    return maxRobotsCount;
}

Python

from collections import deque


def count_max_robots(charge_times: list[int], running_costs: list[int], budget: int):  # LeetCode Q.2398.
    max_robots_count = 0  # Base case.

    window_total_cost = 0

    queue: deque[tuple[int, int]] = deque([])  # Format: (charge time, idx).

    start_idx = 0
    for end_idx, charge_time in enumerate(charge_times):
        window_total_cost += running_costs[end_idx]

        while queue and queue[-1][0] <= charge_time:
            queue.pop()

        queue.append((charge_time, end_idx))

        robots_count = end_idx + 1 - start_idx
        max_charge_time = queue[0][0]

        while budget < max_charge_time + robots_count * window_total_cost:
            window_total_cost -= running_costs[start_idx]

            robots_count -= 1
            start_idx += 1

            if queue and queue[0][1] < start_idx: queue.popleft()

            if start_idx > end_idx: break  # 0 robots at hand.

        if robots_count > max_robots_count: max_robots_count = robots_count

    return max_robots_count

Follow-up Problem

Looking back, do you still think the requirement to select consecutive robots was just a redundant constraint? 🤓