A throttled function runs at most once every d milliseconds. This version uses the leading edge: a call runs immediately if at least d milliseconds have passed since the last call that ran; otherwise the call is dropped.
Given the times of n calls in non-decreasing order, print the times of the calls that actually run.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ d ≤ 10^6
- 0 ≤ each time ≤ 10^9, non-decreasing
Input and output
- Input
- Line 1: n and d Line 2: n call times
- Output
- The times of the calls that run, separated by single spaces.
Examples
Input 1
6 10
0 3 10 12 25 34Output
0 10 250 runs; 3 is too soon; 10 is exactly 10 later so it runs; 12 is too soon; 25 runs; 34 is only 9 after 25.
Input 2
3 1
4 5 6Output
4 5 6With d = 1 every distinct time runs.
Show hints
- Remember only the time of the last call that ran.
Show the explanation
Keep last, the time of the last call that ran (start with "none"). For each call at time t, run it if there is no last yet or t − last ≥ d, and then set last = t. Dropped calls do not move last.
The same idea appears in real throttle helpers used for scroll and resize handlers: a closure stores the last run time and compares it with Date.now().
Compare with debounce: throttle guarantees regular runs during a long burst; debounce waits until the burst ends.
Original UniCircle question. Last reviewed 22 Oct 2026.