2676. Throttle


Problem Description

The given problem describes a scenario where we need to create a version of a function that is "throttled." Throttling in this context means that after the function is called once, it cannot be called again for a specified duration t (in milliseconds). This ensures that the function doesn't execute too frequently within a short time frame. If the function is triggered again during the throttle period, the parameters (arguments) of this call are saved but not immediately acted upon. Instead, once the throttle period elapses, the function should be executed with the latest saved arguments, resetting the throttle timer for another t milliseconds. This effect is like postponing all function calls within the throttle period, and only the latest call's arguments are considered when the throttle period ends.

To further simplify:

  1. Call the function immediately if not within a throttle period.
  2. If a function call is made during a throttle period, store the latest arguments.
  3. When the throttle period ends, call the function with the last stored arguments (if any) and start a new throttle period.

An illustration provided shows the effect of throttle over time, emphasizing that only the latest inputs are executed after each throttle period.

Intuition

To achieve the throttling behavior, we maintain a state to track whether we are in a "pending" or throttle period. If the function is not in the pending state, we call it immediately and set it to pending. During this pending state, all subsequent calls will not trigger an immediate function execution but will update the arguments that the function will use after the pending state is resolved.

Here's a breakdown of the solution approach:

  1. Initialize a pending state to false and a variable nextArgs to store the latest arguments during the pending state.
  2. Create a wrapper function that encapsulates the throttling logic:
    • If pending is false, call the function immediately with the provided arguments and set pending to true. This starts the throttle period.
    • Afterwards, for any calls received during the throttle period (when pending is true), only update nextArgs with the latest arguments.
  3. Set a setTimeout with the duration t that will reset the pending state to false after the specified time. It will also check if there are nextArgs stored, and if so, call the wrapper function with these arguments, effectively queuing the next execution and starting a new throttle period.

This approach ensures that the function is executed at the correct time intervals while discarding all intermediate calls except for the last one before the end of the throttle period.

Solution Approach

The solution implements throttling using closures and a simple state management system to track when the function should be executed or delayed. Here's a step-by-step breakdown of the algorithm:

  1. State Tracking: Two important pieces of state are maintained:

    • A boolean pending flag, which is initially set to false and indicates whether the function is currently in a throttled period.
    • A variable nextArgs, which will store the arguments passed to the most recent call that occurred during the throttle period.
  2. Closure and the Wrapper Function: A wrapper function is defined, which will be returned by the throttle function. The wrapper function serves as the throttled version of the original fn. Closures allow the wrapper to have access to the pending and nextArgs variables even after the throttle function has finished execution.

  3. Immediate Execution: If the function is not currently in a pending state (throttle period), it is executed immediately with the given arguments, and pending is set to true.

  4. Setting Throttle Period: After the first execution, a setTimeout is set for the duration t milliseconds. This timeout represents the delay during which the function cannot be executed again.

  5. Handling Subsequent Calls: If the wrapper is called again within the duration t (while pending is true), the arguments are stored in nextArgs. These arguments will be used for the next execution. If further calls are made during the delay, they only update nextArgs with the latest arguments, and the previous stored arguments are discarded.

  6. End of Throttle Period: Once the timer (setTimeout) completes, it will set pending to false, indicating that the throttle period has ended. If there were any calls during the delay period (nextArgs is not undefined), the wrapper function is called again with the last stored arguments, and a new throttle period begins.

  7. Continuous Throttling: The cycle continues with the wrapper function being executed at most once per every t milliseconds with the latest arguments that were passed to it during the previous throttle period.

Here's a high-level overview of the coding pattern used:

1const throttle = (fn: F, t: number): F => {
2    let pending = false;
3    let nextArgs;
4    const wrapper = (...args) => {
5        nextArgs = args;
6        if (!pending) {
7            fn(...args);
8            pending = true;
9            nextArgs = undefined;
10            setTimeout(() => {
11                pending = false;
12                if (nextArgs) wrapper(...nextArgs);
13            }, t);
14        }
15    };
16    return wrapper;
17};

The primary data structure used is the JavaScript variable, while the predominant pattern is the use of closure and timer (setTimeout) for managing the throttle state. This implementation ensures a function is throttled effectively, and its latest call arguments are respected.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

Let's illustrate the solution approach with a simple example. Suppose we have a function logMessage that takes a string message as an argument and prints it. We want to throttle this function such that it only executes once every 2 seconds, despite being called multiple times.

Here's the logMessage function:

1function logMessage(message) {
2    console.log(message);
3}

We'll create a throttled version of logMessage using the throttle function provided in the solution approach.

1const throttledLogMessage = throttle(logMessage, 2000);

Now let's simulate a series of calls to throttledLogMessage with different messages:

1throttledLogMessage("First call - Immediate");  // Executed immediately
2throttledLogMessage("Second call - Discarded"); // Ignored during throttle period
3setTimeout(() => throttledLogMessage("Third call - 2s later"), 500);  // Ignored, still in throttle period
4setTimeout(() => throttledLogMessage("Fourth call - 2.5s later"), 2500); // Executed after throttle period with these arguments

Here's how the throttling mechanism processes each call:

  1. The first call to throttledLogMessage("First call - Immediate") executes immediately because we are not in a throttle period, prints "First call - Immediate", and starts the 2-second throttle period.

  2. During the throttle period (2 seconds), any calls to throttledLogMessage do not execute immediately. The second call's arguments are stored, but are soon overwritten by the third call's arguments, as it is the most recent before the timeout finishes.

  3. The setTimeout callback set during the first call times out after 2 seconds, ending the throttle period and checking nextArgs. It finds that nextArgs contains arguments from the third call and executes throttledLogMessage("Third call - 2s later"). However, since we deliberately placed the fourth call outside of the throttled period (2.5 seconds later), it becomes the pending arguments (not the third call).

  4. The call with "Fourth call - 2.5s later" is then executed, and a new throttle period starts.

After all these calls, the printed messages to the console will be:

1First call - Immediate
2Fourth call - 2.5s later

This example demonstrates how the solution makes use of closures, state variables (pending, nextArgs), and the setTimeout function to throttle calls, ensuring the function execution is spaced out by at least 2 seconds and that only the most recent call's arguments are used.

Solution Implementation

1from typing import Callable, Any, List
2import threading
3import time
4
5# Type definition for a function that accepts any number of arguments of any type.
6FunctionWithAnyArgs = Callable[..., None]
7
8def throttle(fn: FunctionWithAnyArgs, delay: float) -> FunctionWithAnyArgs:
9    """
10    Creates a throttled function that only invokes the provided function at most once per every `delay` seconds.
11  
12    :param fn: The function to throttle.
13    :param delay: The number of seconds to throttle invocations to.
14    :returns: A new throttled version of the provided function.
15    """
16    # Flag to indicate if there is a pending function execution.
17    is_pending = False
18    # An array to store the latest arguments with which to call the function when it becomes available.
19    next_args: List[Any] = []
20    # Lock to synchronize access to shared data.
21    lock = threading.Lock()
22  
23    def reset_pending():
24        nonlocal is_pending, next_args
25        with lock:
26            is_pending = False
27            if next_args:
28                # If there are pending arguments, invoke the wrapper function with them.
29                throttled_wrapper(*next_args)
30                # Clear the arguments once they've been used.
31                next_args = []
32  
33    def throttled_wrapper(*args: Any) -> None:
34        nonlocal is_pending, next_args
35        with lock:
36            next_args = args  # Store the latest arguments.
37            if not is_pending:  # If there is no pending execution, proceed.
38                fn(*args)  # Call the original function immediately with the provided arguments.
39                is_pending = True  # Set the flag to True to prevent immediate succeeding calls.
40                # Start a timer that will reset the flag and call the wrapper if there are pending arguments.
41                threading.Timer(delay, reset_pending).start()
42  
43    return throttled_wrapper  # Return the throttled version of the function.
44
45# Usage example:
46# def print_log(message):
47#     print(message)
48# 
49# throttled_log = throttle(print_log, 0.1)
50# throttled_log("log")  # This log statement is executed immediately.
51# time.sleep(0.05)
52# throttled_log("log")  # This log statement will be executed after the delay (t=0.1s) due to throttling.
53
1import java.util.Timer;
2import java.util.TimerTask;
3
4// Interface to represent any function that can take any number of arguments.
5interface FunctionWithAnyArgs {
6    void call(Object... args);
7}
8
9public class Throttler {
10    /**
11     * Creates a throttled function that only invokes the provided function
12     * at most once per every 'delay' milliseconds.
13     *
14     * @param fn    The function to throttle.
15     * @param delay The number of milliseconds to throttle invocations to.
16     * @return A new throttled version of the provided function.
17     */
18    public static FunctionWithAnyArgs throttle(FunctionWithAnyArgs fn, long delay) {
19        // Object to hold the state of the throttle mechanism.
20        final Object state = new Object() {
21            boolean isPending = false;
22            Object[] nextArgs = null;
23            Timer timer = new Timer();
24        };
25
26        // The wrapper function that manages the invocation of the original function with throttling.
27        return (Object... args) -> {
28            synchronized (state) {
29                state.nextArgs = args; // Store the latest arguments.
30                if (!state.isPending) { // If there is no pending execution, proceed.
31                    fn.call(args); // Call the original function immediately with the provided arguments.
32                    state.isPending = true; // Set the flag to true to prevent immediate succeeding calls.
33                    state.nextArgs = null;  // Clear the arguments since the function has been called.
34
35                    // After `delay` milliseconds, reset the flag and call the wrapper if there are pending arguments.
36                    state.timer.schedule(new TimerTask() {
37                        @Override
38                        public void run() {
39                            synchronized (state) {
40                                state.isPending = false;
41                                if (state.nextArgs != null) { // If there are pending arguments, invoke the wrapper function with them.
42                                    fn.call(state.nextArgs);
43                                    state.nextArgs = null; // Clear nextArgs after the invocation.
44                                }
45                            }
46                        }
47                    }, delay);
48                }
49            }
50        };
51    }
52
53    // Usage example within a main method or any other method:
54    public static void main(String[] args) {
55        FunctionWithAnyArgs throttledLog = throttle((Object... logArgs) -> {
56            // Assume we're printing the first argument for simplicity, real-world use might differ
57            if (logArgs.length > 0) {
58                System.out.println(logArgs[0]);
59            }
60        }, 100);
61
62        // This log statement is executed immediately.
63        throttledLog.call("log1");
64        // The following log statement will be rescheduled to execute after the throttling delay.
65        new Timer().schedule(new TimerTask() {
66            @Override
67            public void run() {
68                throttledLog.call("log2");
69            }
70        }, 50);
71    }
72}
73
1#include <functional>
2#include <chrono>
3#include <thread>
4#include <vector>
5#include <mutex>
6
7// Type for a function that accepts any number of arguments of any type.
8using FunctionWithAnyArgs = std::function<void()>;
9
10class Throttler {
11private:
12    FunctionWithAnyArgs fn;
13    int delay;
14    bool isPending;
15    std::mutex mtx;
16
17public:
18    Throttler(const FunctionWithAnyArgs& fn, int delay) 
19    : fn(fn), delay(delay), isPending(false) {}
20
21    // Wrapper function that manages the invocation of the original function with throttling.
22    template<typename... Args>
23    void operator()(Args... args) {
24        std::unique_lock<std::mutex> lock(mtx);
25        if (!isPending) { // If there is no pending execution, proceed.
26            fn(); // Call the original function immediately with the provided arguments.
27            isPending = true; // Set the flag to true to prevent immediate succeeding calls.
28            lock.unlock(); // Unlock the mutex before sleeping the thread.
29          
30            std::thread([this](){
31                std::this_thread::sleep_for(std::chrono::milliseconds(delay));
32              
33                std::lock_guard<std::mutex> guard(this->mtx); 
34                this->isPending = false; // After `delay` milliseconds, reset the flag.
35            }).detach();
36        }
37    }
38};
39
40// Usage example:
41int main() {
42    // Creates a throttled function that prints the argument to console.
43    Throttler throttledPrint([]() {
44        std::cout << "Print function called." << std::endl;
45    }, 100);
46
47    throttledPrint(); // This print function is executed immediately.
48  
49    // Simulate a call to the function after a short delay.
50    std::this_thread::sleep_for(std::chrono::milliseconds(50));
51    throttledPrint(); // Due to throttling, this call doesn't do anything.
52  
53    // Wait some extra time to see the effects.
54    std::this_thread::sleep_for(std::chrono::milliseconds(200));
55
56    return 0;
57}
58
1type FunctionWithAnyArgs = (...args: any[]) => void; // Type for a function that accepts any number of arguments of any type.
2
3/**
4 * Creates a throttled function that only invokes the provided function at most once per every `delay` milliseconds.
5 * 
6 * @param fn - The function to throttle.
7 * @param delay - The number of milliseconds to throttle invocations to.
8 * @returns A new throttled version of the provided function.
9 */
10const throttle = (fn: FunctionWithAnyArgs, delay: number): FunctionWithAnyArgs => {
11    // Flag to indicate if there is a pending function execution.
12    let isPending = false;
13    // An array to store the latest arguments with which to call the function when it becomes available.
14    let nextArgs: any[] | undefined;
15  
16    /**
17     * The wrapper function that manages the invocation of the original function with throttling.
18     *
19     * @param args - Arguments with which the function is expected to be called.
20     */
21    const throttledWrapper = (...args: any[]): void => {
22        nextArgs = args; // Store the latest arguments.
23        if (!isPending) { // If there is no pending execution, proceed.
24            fn(...args); // Call the original function immediately with the provided arguments.
25            isPending = true; // Set the flag to true to prevent immediate succeeding calls.
26            nextArgs = undefined; // Clear the arguments since the function has been called.
27            setTimeout(() => { // After `delay` milliseconds, reset the flag and call the wrapper if there are pending arguments.
28                isPending = false;
29                if (nextArgs) throttledWrapper(...nextArgs); // If there are pending arguments, invoke the wrapper function with them.
30            }, delay);
31        }
32    };
33
34    return throttledWrapper; // Return the throttled version of the function.
35};
36
37// Usage example:
38// const throttledLog = throttle(console.log, 100);
39// throttledLog("log"); // This log statement is executed immediately.
40// setTimeout(() => throttledLog("log"), 50); // This log statement will be executed at t=100ms (due to throttling).
41

Time and Space Complexity

The time complexity of the throttle function is O(1) for each call, regardless of the value of t. This is because each function call involves only a constant number of operations: setting variables, checking conditions, and possibly scheduling a setTimeout. The actual throttled function fn is called at most once every t milliseconds; however, the complexity of fn itself does not affect the throttling mechanism.

The space complexity of the throttle function is O(1). This is because there are a fixed number of variables used (pending, nextArgs, and wrapper), and their sizes do not depend on the number of times wrapper is called or the size of the input to fn. However, be aware that if the fn function being throttled captures a large scope or requires significant memory, that would affect the overall space complexity of the system using the throttle, but not the throttle implementation itself.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄