How long until a slower response

MediumAbout 25 minProblem 2 of 2 in StacksDraft

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

  1. waitForSlower([120, 90, 110, 150, 100])returns [3, 1, 1, 0, 0]
  2. waitForSlower([50, 50, 60])returns [2, 1, 0]Equal is not slower.
  3. 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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open