How long until a slower response
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A probe records one response time per minute. For alerting, you want to know, for each minute, how many minutes pass until a strictly slower response is recorded.
Return a list of the same length: for minute i, the number of minutes until the first later minute with a higher latency, or 0 if none comes.
- 0 ≤ latencies.length ≤ 200,000
- 0 ≤ latencies[i] ≤ 10⁶
Examples
waitForSlower([120, 90, 110, 150, 100])returns[3, 1, 1, 0, 0]waitForSlower([50, 50, 60])returns[2, 1, 0]Equal is not slower.waitForSlower([])returns[]
Hints
Hint 1 of 2
Scanning forward from every minute is quadratic when latencies keep falling. Which minutes are still waiting for an answer?
Hint 2 of 2
Keep a stack of positions still waiting. When a new latency arrives, it answers every waiting minute on top with a lower latency: pop them and record the distance.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Scanning forward from each minute is quadratic when latencies keep falling: every minute scans to the end and finds nothing.
Turn it around. Keep a stack of minutes that have not found a slower response yet. Their latencies never increase from bottom to top, because a higher latency would already have answered the ones below it. When a new minute arrives, it answers every waiting minute on top with a strictly lower latency; pop each and record the distance. Then the new minute waits too.
Each minute is pushed once and popped at most once, so the whole pass is linear. Whatever is still on the stack at the end never saw a slower response and keeps its 0. Use <, not <=: an equal latency is not slower.
function waitForSlower(latencies) {
const out = new Array(latencies.length).fill(0);
const waiting = [];
for (let i = 0; i < latencies.length; i++) {
while (waiting.length && latencies[waiting[waiting.length - 1]] < latencies[i]) {
const j = waiting.pop();
out[j] = i - j;
}
waiting.push(i);
}
return out;
}Complexity. O(n) time, O(n) space for the stack and the answer.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.