Best Moment to Stay Calm
MediumSliding Window
Problem
A café owner knows how many customers arrive each minute (customers[i]) and whether they will be in a bad mood that minute (unhappy[i] = 1) or not (unhappy[i] = 0). Customers arriving in a bad-mood minute leave unsatisfied; all others are satisfied.
With a breathing technique the owner can stay calm for one block of `minutes` consecutive minutes, during which nobody leaves unsatisfied. Return the maximum number of satisfied customers.
Example 1
- Input:
- customers = [2, 0, 3, 1, 4], unhappy = [0, 1, 1, 0, 1], minutes = 2
- Output:
- 7
Without the technique 2 + 1 = 3 are satisfied. Staying calm in minutes 3–4 recovers the 4 customers of minute 4: 3 + 4 = 7.
Example 2
- Input:
- customers = [5], unhappy = [1], minutes = 1
- Output:
- 5
Constraints
- 1 ≤ minutes ≤ customers.length = unhappy.length ≤ 10^5
- 0 ≤ customers[i] ≤ 1000
- unhappy[i] is 0 or 1
Hint
Show the first hint
Split the answer into customers who are satisfied anyway, plus the extra ones the calm block rescues.
Walkthrough
How to approach it
01Clarify before coding
- Must the calm block be used? Using it never hurts, so assume it is.
- Can it be partial at the end of the day? No, it is a full block of minutes inside the day.
- Does it matter in calm minutes whether the owner was going to be in a good mood? No, those customers are counted once in the baseline.
02Brute force
For each start of the calm block, recount the satisfied customers over the whole day.
Cost: O(n·(n - minutes)) ≈ O(n²) time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.