⚡Flashcard Drill➔
NeetCode #959LC-2676MediumJavaScript
← Back to All Problems

#959 · #2676 · Throttle(节流)

📌 Problem Statement & Constraints

Implement throttle(fn, t): return a wrapper that invokes fn at most once in any window of t milliseconds; a call suppressed inside a window is replayed with the latest arguments when the window ends.

💡 Core Algorithmic Approaches

  1. Track nextCall, the timestamp when the next call becomes legal, and pending, the suppressed arguments.
  2. If now >= nextCall, invoke immediately and set nextCall = now + t.
  3. Otherwise store the arguments in pending and schedule a setTimeout for nextCall - now to replay them.
  4. On replay, clear pending and reset nextCall. The two distinct moments are the immediate leading call and the trailing replay.

💻 Benchmark Python3 Implementation

var throttle = function(fn, t) {
    let nextCall = 0;                         // timestamp when the next call is allowed
    let pending = null;                       // suppressed arguments
    return function(...args) {
        const now = Date.now();
        if (now >= nextCall) {
            nextCall = now + t;
            fn(...args);
        } else {
            pending = args;
            setTimeout(() => {
                if (pending !== null) {
                    const a = pending;
                    pending = null;
                    nextCall = Date.now() + t;
                    fn(...a);
                }
            }, nextCall - now);
        }
    };
};

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): constant time per call.
💾 Space Complexity
O(1): two state variables and at most one timer.

⚠️ Interview Pitfalls & Follow-ups

  • Dropping suppressed calls entirely: the problem requires replaying the last one.
  • Creating a new timer on every suppressed call: that causes duplicate executions; guard with the pending check.
  • Not resetting nextCall after a replay: later throttle windows would break.
  • Worrying that nextCall = 0 blocks the first call: Date.now() is far larger than 0, so the first call runs immediately.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related JavaScript Problems