Maximum Number of Robots Within Budget - Practice Coding Problems

Maximum Number of Robots Within Budget - Problem

Array Binary Search Queue Sliding Window Heap (Priority Queue) Prefix Sum Monotonic Queue Hard

You are the manager of a robotic manufacturing plant and need to optimize the operation of your robots within a limited budget. You have n robots available, each with different charging and operational costs.

Given two arrays:

chargeTimes[i] - the cost to charge the i-th robot
runningCosts[i] - the ongoing operational cost per unit time for the i-th robot

The total cost of running k consecutive robots is calculated as:

Total Cost = max(chargeTimes) + k × sum(runningCosts)

Where max(chargeTimes) is the highest charging cost among the selected robots, and sum(runningCosts) is the sum of all operational costs.

Goal: Find the maximum number of consecutive robots you can operate without exceeding your budget.

Input & Output

example_1.py — Basic Case

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

› Output: 3

💡 Note: We can run robots [1,2,3] with charge times [6,1,3] and running costs [1,3,4]. Total cost = max(6,1,3) + 3×(1+3+4) = 6 + 24 = 30 > budget. Let's try [0,1,2]: max(3,6,1) + 3×(2+1+3) = 6 + 18 = 24 ≤ 25. We can run 3 consecutive robots.

example_2.py — Small Budget

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

› Output: 0

💡 Note: Even running a single robot costs at least 11 + 1×10 = 21 > 19, so we cannot run any robots within the budget.

example_3.py — Large Budget

$ Input: chargeTimes = [1,1,1,1], runningCosts = [1,1,1,1], budget = 50

› Output: 4

💡 Note: We can run all robots. Total cost = max(1,1,1,1) + 4×(1+1+1+1) = 1 + 16 = 17 ≤ 50. All 4 consecutive robots can be operated.

Constraints

1 ≤ chargeTimes.length == runningCosts.length ≤ 5 × 10⁴
1 ≤ chargeTimes[i], runningCosts[i] ≤ 10⁵
1 ≤ budget ≤ 10¹⁵
All robots must be consecutive in the array

Visualization

Tap to expand

Understanding the Visualization

Setup Cost Analysis

Each machine has a one-time setup cost (charge time) and ongoing operational cost

Window Selection

Choose consecutive machines, pay highest setup cost once, plus all operational costs

Sliding Window Optimization

Use two pointers to efficiently explore all possible consecutive selections

Maximum Tracking

Maintain maximum setup cost using monotonic deque for O(1) updates

Key Takeaway

🎯 Key Insight: Use sliding window with monotonic deque to efficiently track maximum charge cost while exploring all consecutive robot combinations in linear time.

Asked in

G Google 15 a Amazon 12 f Meta 8 ⊞ Microsoft 6

The optimal solution uses a sliding window approach with monotonic deque to efficiently track the maximum charge cost. We expand the window when possible and contract when over budget, achieving O(n) time complexity. The key insight is that each element enters and leaves the deque at most once, making the solution highly efficient.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Two Pointers	O(n)	O(n)	Use sliding window technique with efficient maximum tracking
Binary Search on Answer	O(n log n)	O(n)	Binary search on the maximum number of robots with sliding window verification
Brute Force (Check All Subarrays)	O(n³)	O(1)	Check every possible consecutive subarray and find the longest one within budget

Sliding Window with Two Pointers — Algorithm Steps

Initialize left and right pointers, running cost sum, and a deque for maximum tracking
Expand right pointer and add new robot to window
Update running cost sum and maintain maximum in deque
If cost exceeds budget, contract left pointer
Track maximum valid window size seen so far

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize window

Start with empty window, left=right=0

Expand right pointer

Add robots while maintaining deque order

Check budget constraint

Calculate cost using deque front for max

Contract if needed

Move left pointer when over budget

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int maximumRobots(int* chargeTimes, int chargeTimesSize, int* runningCosts, int runningCostsSize, long long budget) {
    int n = chargeTimesSize;
    int left = 0;
    int maxRobots = 0;
    long long runningSum = 0;
    int* maxDeque = (int*)malloc(n * sizeof(int));
    int front = 0, back = -1;
    
    for (int right = 0; right < n; right++) {
        // Add current robot to window
        runningSum += runningCosts[right];
        
        // Maintain decreasing order in deque
        while (front <= back && chargeTimes[maxDeque[back]] <= chargeTimes[right]) {
            back--;
        }
        maxDeque[++back] = right;
        
        // Contract window if cost exceeds budget
        while (left <= right && front <= back) {
            int windowSize = right - left + 1;
            long long maxCharge = chargeTimes[maxDeque[front]];
            long long totalCost = maxCharge + (long long)windowSize * runningSum;
            
            if (totalCost <= budget) {
                if (windowSize > maxRobots) {
                    maxRobots = windowSize;
                }
                break;
            } else {
                // Remove leftmost robot
                if (maxDeque[front] == left) {
                    front++;
                }
                runningSum -= runningCosts[left];
                left++;
            }
        }
    }
    
    free(maxDeque);
    return maxRobots;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is added and removed from deque at most once

✓ Linear Growth

Space Complexity

O(n)

Deque can store up to n elements in worst case

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler