LeetCode 2398 - Maximum Number of Robots Within Budget

This problem asks us to determine the maximum number of consecutive robots that can be run without exceeding a given budget. We are given two arrays of length n: chargeTimes and runningCosts.

leetcodehardarraybinary-searchqueuesliding-windowheap-(priority-queue)prefix-summonotonic-queue

LeetCode Problem 2398

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue

Solution

Problem Understanding

This problem asks us to determine the maximum number of consecutive robots that can be run without exceeding a given budget. We are given two arrays of length n: chargeTimes and runningCosts. For any consecutive subset of k robots, the total cost is computed as:

total_cost = max(chargeTimes of the k robots) + k * sum(runningCosts of the k robots)

The objective is to find the largest k such that the total cost does not exceed budget.

In other words, we need to slide a window over the robots, compute the cost for each window, and track the maximum window length that fits within the budget. The constraints are substantial: n can be up to 50,000, and budget can be as large as 10^15. Therefore, naive solutions that examine every possible consecutive subset will be too slow. The problem guarantees that both chargeTimes and runningCosts are positive integers, which simplifies certain calculations.

Important edge cases include situations where no robot can be run within the budget, only a single robot can be run, or all robots can be run without exceeding the budget.

Approaches

The brute-force approach would involve checking all possible consecutive windows of robots. For each window, compute max(chargeTimes) and sum(runningCosts), then calculate the total cost. This approach is correct because it directly evaluates the total cost formula. However, it is extremely inefficient because the number of windows grows quadratically (O(n^2)) and computing max and sum for each window requires additional time. With n up to 50,000, this approach is computationally infeasible.

The optimal approach uses a sliding window combined with a monotonic queue (deque) to track the maximum charge time efficiently. While moving the right end of the window forward, we maintain a running sum of runningCosts and update the deque to reflect the current maximum chargeTimes in the window. If the total cost exceeds the budget, we move the left end of the window forward, adjusting the running sum and deque accordingly. This approach guarantees linear-time performance relative to the input size because each element is added and removed from the deque at most once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) or O(n) Checks all consecutive windows; inefficient for large n
Optimal O(n) O(n) Sliding window with monotonic deque for max charge; tracks running sum efficiently

Algorithm Walkthrough

  1. Initialize two pointers, left and right, to define the sliding window. Initialize a running sum window_sum for runningCosts and a deque max_charge_deque to maintain indices of chargeTimes in decreasing order.
  2. Iterate right over the array from 0 to n-1. For each right:
  • Add runningCosts[right] to window_sum.
  • Maintain the deque such that chargeTimes[max_charge_deque[0]] is the maximum in the current window. Remove indices from the deque's back if their chargeTimes are smaller than chargeTimes[right], then append right.
  1. While the total cost max(chargeTimes in window) + window_length * window_sum exceeds budget, move left forward:
  • Subtract runningCosts[left] from window_sum.
  • Remove left from the deque if it is at the front.
  • Increment left.
  1. Update the maximum window length as right - left + 1 whenever the total cost is within budget.
  2. Continue until right reaches the end of the array. Return the maximum window length.

Why it works: The deque ensures max(chargeTimes) can be retrieved in O(1) time for any window. The sliding window guarantees all consecutive segments are checked exactly once. The algorithm maintains the correct running sum and maximum as the window expands and contracts, producing the correct maximum number of robots that can run within budget.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        n = len(chargeTimes)
        max_charge_deque = deque()
        left = 0
        window_sum = 0
        max_len = 0

        for right in range(n):
            window_sum += runningCosts[right]
            
            while max_charge_deque and chargeTimes[max_charge_deque[-1]] <= chargeTimes[right]:
                max_charge_deque.pop()
            max_charge_deque.append(right)
            
            while max_charge_deque and chargeTimes[max_charge_deque[0]] + (right - left + 1) * window_sum > budget:
                if max_charge_deque[0] == left:
                    max_charge_deque.popleft()
                window_sum -= runningCosts[left]
                left += 1
            
            max_len = max(max_len, right - left + 1)
        
        return max_len

The Python implementation carefully maintains a running sum of runningCosts and a deque that tracks the indices of chargeTimes in decreasing order. This allows retrieving the maximum chargeTimes in O(1) time. The sliding window contracts whenever the budget is exceeded, ensuring all windows are valid, and updates the maximum length accordingly.

Go Solution

package main

func maximumRobots(chargeTimes []int, runningCosts []int, budget int64) int {
    n := len(chargeTimes)
    maxLen := 0
    left := 0
    windowSum := int64(0)
    deque := []int{}

    for right := 0; right < n; right++ {
        windowSum += int64(runningCosts[right])

        for len(deque) > 0 && chargeTimes[deque[len(deque)-1]] <= chargeTimes[right] {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, right)

        for len(deque) > 0 && int64(chargeTimes[deque[0]])+int64(right-left+1)*windowSum > budget {
            if deque[0] == left {
                deque = deque[1:]
            }
            windowSum -= int64(runningCosts[left])
            left++
        }

        if currentLen := right - left + 1; currentLen > maxLen {
            maxLen = currentLen
        }
    }

    return maxLen
}

In Go, care is taken to use int64 for windowSum to prevent integer overflow because budget can be as large as 10^15. Slice operations mimic deque operations in Python. The logic for sliding window and maintaining the max element is identical.

Worked Examples

Example 1:

chargeTimes = [3,6,1,3,4]
runningCosts = [2,1,3,4,5]
budget = 25

Step through:

right window_sum deque (max indices) total_cost left max_len
0 2 [0] 3+1*2=5 0 1
1 3 [1] 6+2*3=12 0 2
2 6 [1,2] 6+3*6=24 0 3
3 10 [1,3] 6+4*10=46 > 25 1->2->3 3
4 15 [4] 4+2*15=34 > 25 left=4 3

Maximum valid window length is 3.

Example 2:

chargeTimes = [11,12,19]
runningCosts = [10,8,7]
budget = 19

Each robot individually exceeds budget: maximum length is 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is added and removed from deque at most once; sliding window moves in O(n)
Space O(n) Deque can store up to n indices

The sliding window guarantees linear time traversal, and the deque ensures constant time maximum retrieval, giving an overall optimal complexity.

Test Cases

# Basic examples
assert Solution().maximumRobots([3,6,1,3,4], [2,1,3,4,5], 25) == 3  # example 1
assert Solution().maximumRobots([11,12,19], [10,8,7], 19) == 0     # example 2

# Single robot fits
assert Solution().maximumRobots([5], [3], 10) == 1

# Single robot too expensive
assert Solution().maximumRobots([10], [10], 5) == 0

# All robots fit
assert Solution().maximumRobots([1,1,1], [1,1,1], 10) == 3

# Large numbers stress test
assert Solution().maximumRobots([100