2627. Debounce


Problem Description

The core of this problem is to implement a debounced function. When we debounce a function, we're essentially delaying its execution until a certain amount of time (specified in milliseconds) has passed without it being called again. During this time, if the function is called again, the previous pending execution is cancelled, and the delay timer restarts. This is particularly useful in scenarios where the function is expected to be called frequently, but you only want it to execute after some quiet period, such as when the user stops typing in a search field.

It's important to note that the debounced function should be able to receive and pass on any parameters it is called with to the original function once the debounce time has elapsed without new calls.

Considering the examples provided, if the debounce time t is set to 50ms:

  • If the function is called at 30ms, 60ms, and 100ms, the first two calls will be cancelled, and only the third call will actually be executed at 150ms.
  • If the debounce time t is 35ms, the call at 30ms will be cancelled due to the call at 60ms, but the call at 60ms will execute at 95ms. The last call at 100ms will then execute at 135ms

Intuition

To implement the debounced function without external libraries like lodash, we start by defining a function that takes in two parameters: the function to be debounced fn and the debounce time t. Within our debounce implementation, we maintain a timeout variable that holds a reference to a timer created with setTimeout. This timer is responsible for actually calling our fn function after the delay t.

  • Each time the debounced function is called, we check if there's an existing timeout timer running (which would mean a previous call is waiting to execute).
  • If there is, we clear this timer using clearTimeout to cancel the previous call.
  • We then set a new timeout with the delay t to call our fn function with the current set of arguments args. We use fn.apply(this, args) to ensure the function is called with the correct context (this) and arguments.

It is essential that we clear the previous timeout every time our function is called (if it exists) because this enforces the debouncing effect—only allowing the function to execute after t milliseconds have passed since the last call.

Solution Approach

The debounce mechanism relies on two main components: closure and timing control via setTimeout and clearTimeout. Here's how the solution provided makes use of these components:

  1. Closure: We create an inner function within the debounce function that has access to the outer scope. This inner function uses variables fn, t, and timeout which are defined in the outer function's scope. The use of closures ensures that the same timeout variable is used across multiple calls to the debounced function, enabling us to keep track of and control the timer.

  2. Timing Control: The setTimeout function is instrumental in creating the delay mechanism. When it's called, it sets up a timer that, after the specified time t, will execute the provided function—our original function fn applied with the call's arguments. If another call to the debounced function happens before the timer expires, clearTimeout is used to cancel the scheduled execution.

The detailed steps in the debounced function are as follows:

  • We initialize a variable timeout to keep track of the setTimeout timer. It's declared outside the scope of the inner returned function so that it's not reinitialized with each call—this is critical for the debounced function to have memory of previous calls.
  • We return an inner function that captures any arguments it's called with using the rest syntax ...args. This function will act as our debounced function.
  • Within this inner function, we first check if there's an existing timeout (which means a previous call was made within the delay window). If timeout is not undefined, we clear it using clearTimeout. This cancels the prior scheduled execution.
  • Next, we create a new timeout using setTimeout, where we delay the execution of fn for t milliseconds. fn.apply(this, args) ensures that when the function is eventually called, it has the same this value as if the debounced function hadn't been used, and it also passes all the captured arguments (args) correctly.
  • By setting the timeout variable with the result of setTimeout, we maintain a reference to the current timer, which can be cleared if the debounced function is called again within the delay period.

Through this implementation, the debounced function ensures that fn is called only after the debounce time has elapsed since the last invocation. This setup is particularly effective for event-handling scenarios where the frequency of events is high and we need to perform the action once the events have 'settled down.'

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

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Imagine you have developed a search feature in an application that searches for items as the user types in a search box. To improve performance and prevent excessive calls to the search service, you decide to implement a debounced version of the search function.

Consider your basic search function that performs a database query:

1function searchDatabase(query) {
2  console.log(`Searching for: ${query}`);
3  // This would typically involve a database call
4}

You want to ensure that this search function is called only after the user has stopped typing for at least 250ms. Here's how you could use the debouncing approach described above:

  1. Initialization: You write a debounce function as described, which takes in searchDatabase and 250 (the delay in milliseconds) as parameters and returns a new function that you'll use for performing the search.

  2. Execution: The user types 'apple', and on each keystroke, the debounced function is called. The following occurs:

    • User types 'a': searchDatabase is scheduled to be called after 250ms.
    • User types 'p': The previous timeout is cleared, and searchDatabase is scheduled again after 250ms.
    • This process repeats for 'p', 'l', and 'e'.

If the user stops typing after 'e', then:

  1. Completion: Since no new keystrokes occurred for 250ms, the searchDatabase function is finally called with the complete query 'apple'.

The debounced function usage would look like this:

1// This creates the debounced search function
2let debouncedSearch = debounce(searchDatabase, 250);
3
4// This simulates the user typing in the search box
5debouncedSearch('a');
6setTimeout(() => debouncedSearch('ap'), 100);  // After 100ms
7setTimeout(() => debouncedSearch('app'), 160); // After another 60ms
8setTimeout(() => debouncedSearch('appl'), 220); // After another 60ms
9setTimeout(() => debouncedSearch('apple'), 400); // After another 180ms, total 400ms since first key stroke

What happens in this scenario is as follows:

  • At 0ms, the user types 'a', and a timer is set to trigger in 250ms.
  • At 100ms, the user types 'p', the previous timer is cleared, and a new timer is set.
  • This repeats until the user types 'e' at 400ms. Since the user does not type any further, the last timer is not cleared and searchDatabase('apple') is executed at 650ms (400ms + 250ms).

In this way, the debounced function ensures that searchDatabase is not called constantly but only after a 250ms pause in typing, optimizing the search function's performance by reducing unnecessary database calls.

Solution Implementation

1from typing import Callable
2import threading
3
4# Type alias for a generic function that can take any number of parameters of any type
5GenericFunction = Callable[..., any]
6
7def debounce(target_function: GenericFunction, delay: int) -> GenericFunction:
8    """
9    Creates a debounced version of a function that delays invoking the `target_function`
10    until after `delay` milliseconds have elapsed since the last time the debounced
11    function was invoked.
12  
13    :param target_function: The function to debounce.
14    :param delay: The number of milliseconds to delay; afterwards the `target_function` is called.
15    :return: A new debounced version of the `target_function`.
16    """
17    # Variable to hold the timer object
18    timer = None
19
20    def debounced(*args, **kwargs):
21        nonlocal timer
22        # Function that will execute the target function and reset the timer
23        def run_function():
24            nonlocal timer
25            timer = None
26            target_function(*args, **kwargs)
27
28        # If there is an existing timer, cancel it to reset the debounce timer
29        if timer is not None:
30            timer.cancel()
31
32        # Set a new timer to invoke the target function after the specified delay
33        timer = threading.Timer(delay / 1000.0, run_function)
34        timer.start()
35
36    return debounced
37
38# Example usage
39# def print_message(message):
40#     print(message)
41
42# debounced_print = debounce(print_message, 100)
43# debounced_print('Hello')  # Invocation is cancelled
44# debounced_print('Hello')  # Invocation is cancelled
45# debounced_print('World')  # Actually printed to the console after 100ms
46
1import java.util.function.Consumer;
2
3/**
4 * Interface for a generic function that can take any number of parameters of any type.
5 */
6@FunctionalInterface
7interface GenericFunction {
8    void apply(Object... params);
9}
10
11/**
12 * Creates a debounced version of a function that delays invoking the {@code targetFunction}
13 * until after {@code delay} milliseconds have elapsed since the last time the debounced function was invoked.
14 *
15 * @param targetFunction The function to debounce.
16 * @param delay The number of milliseconds to delay; afterwards, the {@code targetFunction} is called.
17 * @return A new debounced version of the {@code targetFunction}.
18 */
19public static GenericFunction debounce(GenericFunction targetFunction, int delay) {
20    // A holder for the timer so we can cancel it
21    final Consumer<Void>[] timerHolder = new Consumer[1];
22
23    // Return the debounced version of the target function
24    return (Object... args) -> {
25        // Cancel the current timer if one exists
26        if (timerHolder[0] != null) {
27            timerHolder[0].accept(null);
28            timerHolder[0] = null;
29        }
30
31        // Create a new timer for the delay period
32        timerHolder[0] = ignored -> new java.util.Timer().schedule(
33            new java.util.TimerTask() {
34                @Override
35                public void run() {
36                    targetFunction.apply(args); // Invoke the target function after the delay
37                }
38            },
39            delay
40        );
41    };
42}
43
44// Example usage
45public static void main(String[] args) {
46    // Create a debounced version of System.out.println
47    GenericFunction debouncedPrint = debounce(params -> System.out.println(params[0]), 100);
48
49    // Call the debounced function multiple times
50    debouncedPrint.apply("Hello"); // Invocation is cancelled
51    debouncedPrint.apply("Hello"); // Invocation is cancelled
52    new java.util.Timer().schedule(new java.util.TimerTask() { // Delay to simulate separation of calls
53        @Override
54        public void run() {
55            debouncedPrint.apply("Hello"); // Actually printed to the console after 100ms
56        }
57    }, 150);
58}
59
1#include <iostream>
2#include <functional>
3#include <chrono>
4#include <thread>
5
6// Type alias for a generic function that can take any number of parameters of any type
7using GenericFunction = std::function<void()>;
8
9/**
10 * Creates a debounced version of a function that delays invoking the `target_function`
11 * until after `delay` milliseconds have elapsed since the last time the debounced function was invoked.
12 * 
13 * @param target_function The function to debounce.
14 * @param delay The number of milliseconds to delay; afterwards, the `target_function` is called.
15 * @return A new debounced version of the `target_function`.
16 */
17GenericFunction debounce(const GenericFunction& target_function, int delay) {
18    // Create a copy of target_function that is mutable
19    auto target_function_copy = target_function;
20
21    // Create a packaged task with the target function inside it
22    std::packaged_task<void()> task(target_function_copy);
23
24    // Variable to hold a future that is associated with the packaged task
25    std::future<void> future = task.get_future();
26
27    // Debounced version of the target function
28    return [=]() mutable {
29         // Static variable to hold the thread that runs the task
30        static std::thread task_thread;
31
32        // If a thread is currently running, join it.
33        if(task_thread.joinable()) {
34            task_thread.join();
35        }
36
37        // Create a new thread to run the task after the specified delay.
38        task_thread = std::thread([=, &task]() {
39            // Sleep for the delay period
40            std::this_thread::sleep_for(std::chrono::milliseconds(delay));
41
42            // Run the task which calls the original target function
43            task();
44        });
45
46        // Detach the thread so it can independently complete its execution
47        task_thread.detach();
48    };
49}
50
51// Main function to demonstrate usage
52int main() {
53    // Example usage of the debounce function
54    auto debounced_log = debounce([]{
55        std::cout << "Hello" << std::endl;
56    }, 100);
57
58    // Invocation is cancelled
59    debounced_log();
60
61    // Invocation is cancelled
62    debounced_log();
63
64    // Actually logged to the console after 100ms
65    debounced_log();
66
67    // Make sure the main thread is kept alive until the debounced log has a chance to execute
68    std::this_thread::sleep_for(std::chrono::milliseconds(200));
69
70    return 0;
71}
72
1// Type alias for a generic function that can take any number of parameters of any type
2type GenericFunction = (...params: any[]) => any;
3
4/**
5 * Creates a debounced version of a function that delays invoking the `targetFunction`
6 * until after `delay` milliseconds have elapsed since the last time the debounced function was invoked.
7 * 
8 * @param targetFunction The function to debounce.
9 * @param delay The number of milliseconds to delay; afterwards, the `targetFunction` is called.
10 * @return A new debounced version of the `targetFunction`.
11 */
12function debounce(targetFunction: GenericFunction, delay: number): GenericFunction {
13    // Variable to hold the timeout identifier
14    let timeoutId: ReturnType<typeof setTimeout> | undefined;
15
16    // Return the debounced version of the target function
17    return function(...args: any[]): void {
18        // If there is an existing timeout, clear it to reset the debounce timer
19        if (timeoutId !== undefined) {
20            clearTimeout(timeoutId);
21        }
22
23        // Set a new timeout to invoke the target function after the specified delay
24        timeoutId = setTimeout(() => {
25            targetFunction.apply(this, args);
26        }, delay);
27    };
28}
29
30// Example usage
31// const debouncedLog = debounce(console.log, 100);
32// debouncedLog('Hello'); // Invocation is cancelled
33// debouncedLog('Hello'); // Invocation is cancelled
34// debouncedLog('Hello'); // Actually logged to the console after 100ms
35

Time and Space Complexity

Time Complexity

The time complexity of the debounce function is primarily dependent on the execution of setTimeout and the operations within the function passed to debounce. Since setTimeout is a native web API that schedules a script to be run after a specified delay and does not block the execution flow, its complexity isn't measured in traditional algorithmic terms. However, it schedules a single delayed function execution, which gives it a constant time operation in this context (O(1)). The time complexity of the actual function fn applied is context-dependent and cannot be determined without specifics about fn. Therefore:

  • Debouncing logic (scheduling and cancelling timeouts): O(1)
  • Invoked function fn: O(f(n)), where f(n) represents the time complexity of fn.

Space Complexity

The space complexity of debounce function includes the space needed for the timeout variable and the arguments passed to fn. The timeout variable either holds a numeric identifier for the created timeout or is undefined. Hence, it consumes constant space (O(1)). The space consumed by arguments (args) depends on the number of arguments and their sizes; however, it is also a constant factor determined by the function's usage, not the debounce function itself. Therefore, space complexity for debounce is:

  • For the closure and timeout identifier: O(1)
  • For arguments and context of fn: O(f(n)), where f(n) represents the space complexity of maintaining the arguments and execution context of fn.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:


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

🪄