Maximum Number of Robots Within Budget

Maximum Number of Robots Within Budget

What is this problem about?

The Maximum Number of Robots Within Budget coding problem gives you two arrays: chargeTimes (charge time for each robot) and runningCosts (running cost for each robot). You are also given a budget. You want to select a contiguous subset of robots such that the total cost (sum of running costs + maximum charge time within the subset) does not exceed the budget. Find the maximum number of robots you can select.

Why is this asked in interviews?

InMobi and Amazon frequently ask this hard problem because it combines sliding window, monotonic queue (or segment tree/sparse table) for range maximum queries, and binary search on the answer. The problem requires carefully optimizing the window calculation and the monotonic property of the answer.

Algorithmic pattern used

Binary Search on Answer + Sliding Window with Monotonic Queue:

1. Binary Search on Length: The maximum number of robots (k) is a monotonic property: if you can select k robots within budget, you can also select any k' < k robots. This allows binary search on the length k of the contiguous subset. The search range is [0, N].
2. check(k) function: For a given length k, we need to determine if there exists any contiguous subset of k robots that satisfies the budget constraint.
   • Use a sliding window of size k.
   • Maintain the sum of runningCosts within the current window. This can be updated in O(1) as the window slides.
   • Maintain the maximum chargeTime within the current window. This is the tricky part. A max_heap could work (O(log k) per operation), but a more efficient monotonic decreasing deque (double-ended queue) allows O(1) amortized time for range maximum queries.
   • As the window slides:
     • Add new robot: Update runningCosts sum. Add chargeTime to monotonic deque (remove smaller elements from back, then add to back).
     • Remove old robot: Update runningCosts sum. Remove chargeTime from front of deque if it's the maximum.
     • Check budget: current_running_costs_sum + current_max_charge_time * k <= budget. If true, check(k) returns true.
   • If no window of size k satisfies the budget, return false.

Time Complexity: O(N * log N) (binary search log N iterations, each check(k) is O(N) with sliding window and monotonic deque).

Example explanation

chargeTimes = [3, 6, 1, 3, 4], runningCosts = [2, 1, 3, 4, 5], budget = 25. Binary search for k in [0, 5].

Try check(k=3): Window 1: robots [3,6,1] from chargeTimes, [2,1,3] from runningCosts. (Indices 0,1,2)

• Max chargeTime in window (3,6,1) = 6.
• Sum runningCosts in window (2,1,3) = 2+1+3 = 6.
• Total cost = 6 + 6 * 3 = 6 + 18 = 24.
• 24 <= 25. Yes! check(3) returns true.

Since check(3) is true, binary search will try for a larger k. (e.g., k=4). Window: k=4. Try chargeTimes=[3,6,1,3], runningCosts=[2,1,3,4].

• Max chargeTime = 6.
• Sum runningCosts = 2+1+3+4 = 10.
• Total cost = 10 + 6 * 4 = 10 + 24 = 34.
• 34 > 25. No. Slide window: chargeTimes=[6,1,3,4], runningCosts=[1,3,4,5].
• Max chargeTime = 6.
• Sum runningCosts = 1+3+4+5 = 13.
• Total cost = 13 + 6 * 4 = 13 + 24 = 37.
• 37 > 25. No.

Binary search will converge to 3.

Common mistakes candidates make

• Naive range maximum query: Using a linear scan or sorting within the sliding window for max_chargeTime makes check(k) O(N*k) or O(N log k), leading to O(N^2 log N) or O(N log^2 N) overall. The monotonic deque is crucial for O(N).
• Off-by-one in window logic: Careful management of left and right pointers and updating sums/deque.
• Integer overflow: max_chargeTime * k can be large; use 64-bit integers if necessary.

Interview preparation tip

For the Array Monotonic Queue Sliding Window Queue Binary Search Heap (Priority Queue) Prefix Sum interview pattern, this problem is a benchmark for combining binary search on the answer with efficient window queries. Mastering the monotonic deque for range maximum/minimum is a must for such problems.