What is the brute force approach and complexity for Maximum Number of Robots Within Budget?

For each start, extend the group with a running max and sum; stop when over budget with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Maximum Number of Robots Within Budget?

Decreasing deque gives the max charge; a running sum gives the rest of the cost with optimal time complexity O(N) and space complexity O(N).

Maximum Number of Robots Within Budget

Q: How do you identify the pattern for Maximum Number of Robots Within Budget?

Look for key signals in the prompt: "consecutive robots" indicates The group is a contiguous range → window.; "maximum number of robots" indicates The window size is the answer → variable window.; "max(chargeTimes) + k × sum(runningCosts)" indicates Needs a window max (deque) plus a window sum (running variable). All positive, so the cost only grows with the window..

Hard·LeetCode #2398 Pro OnlySlight Variation

LeetCode

Problem Statement

This one is rated Hard on LeetCode, but it is the same two tools you already know put together.

There are n robots in a row. Robot i has a charge time chargeTimes[i] and a running cost runningCosts[i]. You also have a budget.

If you run a group of k robots, the total cost is:

max(chargeTimes of the group) + k × sum(runningCosts of the group)

The robots you run must be consecutive in the row. Return the largest k you can run without the total cost going over budget. If not even one robot fits, return 0.

Input

Two integer arrays chargeTimes and runningCosts, both of length n, and a 64-bit integer budget.

Output

A single number: the most consecutive robots whose total cost is ≤ budget.

Example 1

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

Output: 3

Run the first 3 robots: max(3, 6, 1) + 3 × (2 + 1 + 3) = 6 + 18 = 24 ≤ 25. No group of 4 consecutive robots fits.

Example 2

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

Output: 0

Even a single robot costs too much. For example, robot 0 costs 11 + 1 × 10 = 21 > 19.

Constraints

• 1 ≤ n ≤ 5 · 10^4
• 1 ≤ chargeTimes[i], runningCosts[i] ≤ 10^5
• 1 ≤ budget ≤ 10^15
• k × sum can reach about 2.5 · 10^14 — use a 64-bit type.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“consecutive robots”

→ The group is a contiguous range → window.

“maximum number of robots”

→ The window size is the answer → variable window.

“max(chargeTimes) + k × sum(runningCosts)”

→ Needs a window max (deque) plus a window sum (running variable). All positive, so the cost only grows with the window.

Approach Complexity Ladder

Brute Force — every start, grow to the rightO(N²)O(1)

For each start, extend the group with a running max and sum; stop when over budget

Better — sliding window + multisetO(N log N)O(N)

Variable window; running sum for the costs, a multiset for the max charge

Optimal — sliding window + max deque + running sumO(N)O(N)

Decreasing deque gives the max charge; a running sum gives the rest of the cost

Brute Force Intuition

Fix the first robot. Add robots to the right one at a time, keeping a running max charge and a running sum of running costs. Compute the cost each time. When it goes over budget, stop — more robots only cost more.

Recognition rule for this sub-pattern:

You need the max or min of the current window at every step. A deque keeps only elements that could still become the max/min.

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Longest Continuous Subarray With Absolute Diff ≤ Limit Shortest Subarray with Sum at Least K