LeetCode 2627 - Debounce

LeetCode Problem 2627

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to implement a utility function called debounce. The function receives two inputs:

• A function fn
• A delay value t in milliseconds

The goal is to return a new function, called the debounced version of fn.

The behavior of a debounced function is very specific. Every time the returned function is called, it does not execute immediately. Instead, it schedules execution for t milliseconds in the future.

However, if the debounced function is called again before the waiting period finishes, the previously scheduled execution must be cancelled and replaced with a new one.

This means that only the most recent call survives if multiple calls happen within the debounce window.

In other words:

• Every call resets the timer
• Only the last call after a quiet period of length t actually executes
• The executed call must use the latest arguments provided

The problem is fundamentally about managing asynchronous timing behavior using timers.

Consider this sequence:

t = 50

Call at 30ms
Call at 60ms
Call at 100ms

The first call schedules execution at 80ms.

But the second call arrives at 60ms, before 80ms is reached, so the first execution is cancelled. The second call now schedules execution at 110ms.

Then the third call arrives at 100ms, before 110ms is reached, so the second execution is cancelled. The third call schedules execution at 150ms.

As a result, only the final call executes.

The constraints are very small:

• 0 <= t <= 1000
• At most 10 calls are made in the examples

The small constraints tell us that performance is not the main challenge. The real challenge is understanding timer cancellation and closure behavior correctly.

There are several important edge cases:

• Multiple calls occurring before the timer expires
• Calls occurring exactly when another timer would execute
• t = 0, where execution should happen immediately but still respect cancellation semantics
• Functions receiving multiple arguments
• Repeated rapid calls where only the final call should survive

The problem guarantees valid inputs and does not require handling invalid timer values or malformed function arguments.

Approaches

Brute Force Approach

A brute force approach would attempt to track every scheduled execution independently.

For every function call:

1. Create a new timer
2. Store all active timers in a list
3. Cancel older timers whenever a new call arrives
4. Execute only the most recent timer

This works because debounce behavior simply requires removing outdated scheduled executions.

However, maintaining a collection of timers is unnecessary. At any moment, only one timer actually matters, the most recently scheduled one. Older timers are always cancelled immediately when a new call occurs.

This approach introduces extra bookkeeping and unnecessary memory usage.

Optimal Approach

The key observation is that debounce only ever needs to remember one pending timer.

When a new call arrives:

• If a timer already exists, cancel it
• Create a new timer using the latest arguments
• Store the timer reference so it can be cancelled later

This works perfectly because every new invocation invalidates the previous pending execution.

The main tool used here is setTimeout together with clearTimeout.

We also rely on closures so the returned function can remember the active timer between calls.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Stores multiple timers unnecessarily
Optimal	O(1)	O(1)	Maintains only one active timer

Algorithm Walkthrough

1. Create a variable called timer outside the returned function.

This variable stores the currently scheduled timeout. Because it exists in the outer scope, it persists between function calls through closure behavior. 2. Return a new function that accepts any number of arguments.

The debounced function must behave like the original function and support arbitrary parameters. 3. Whenever the debounced function is called, first check whether a timer already exists.

If a previous timer is still pending, it represents an outdated execution request. 4. Cancel the previous timer using clearTimeout(timer).

This ensures the old scheduled execution never happens. 5. Create a new timer using setTimeout.

The new timer schedules execution of fn after t milliseconds. 6. Inside the timeout callback, execute fn(...args).

This ensures the most recent arguments are used. 7. Store the new timeout reference back into timer.

This allows future calls to cancel it if necessary.

Why it works

The algorithm maintains the invariant that at most one execution is pending at any time.

Every new call invalidates the previously scheduled execution and replaces it with a new one. Therefore, only the most recent call after a quiet interval of length t can execute.

Because the timer is always reset on each invocation, the implementation exactly matches debounce semantics.

Python Solution

from typing import Any, Callable
import threading

class Solution:
    def debounce(self, fn: Callable[..., Any], t: int) -> Callable[..., None]:
        timer = None

        def debounced(*args):
            nonlocal timer

            if timer is not None:
                timer.cancel()

            timer = threading.Timer(t / 1000, lambda: fn(*args))
            timer.start()

        return debounced

The implementation begins by creating a timer variable in the outer scope. This variable stores the currently active timer object.

The inner debounced function accepts arbitrary positional arguments using *args. This allows the debounced version to mirror the behavior of the original function.

The nonlocal keyword is necessary because we need to modify the outer timer variable from inside the nested function.

Whenever the debounced function executes, it first checks whether a timer already exists. If so, that timer is cancelled immediately because its execution is no longer valid.

Next, a new timer is created using threading.Timer. Since Python timers operate in seconds while the problem provides milliseconds, we divide t by 1000.

Finally, the new timer starts running and becomes the active pending execution.

Go Solution

package main

import (
	"time"
)

func debounce(fn func(...interface{}), t int) func(...interface{}) {
	var timer *time.Timer

	return func(args ...interface{}) {
		if timer != nil {
			timer.Stop()
		}

		timer = time.AfterFunc(
			time.Duration(t)*time.Millisecond,
			func() {
				fn(args...)
			},
		)
	}
}

The Go implementation follows the same logic as the Python version, but uses Go's time package.

The time.Timer type stores the currently active scheduled execution. When a new call arrives, the existing timer is stopped before a replacement timer is created.

Go uses variadic parameters through ...interface{} to support arbitrary arguments.

Unlike Python, Go does not require a nonlocal keyword because closures automatically capture outer variables by reference.

Worked Examples

Example 1

t = 50

Calls:
50ms -> dlog(1)
75ms -> dlog(2)

Step-by-step trace

Time	Action	Timer State	Result
50ms	Call dlog(1)	Schedule execution at 100ms	Pending
75ms	Call dlog(2)	Cancel previous timer	Old execution removed
75ms	Schedule new timer	Execution at 125ms	Pending
125ms	Timer executes	fn(2) runs	Output produced

Final output:

[(125, [2])]

Example 2

t = 20

Calls:
50ms -> dlog(1)
100ms -> dlog(2)

Step-by-step trace

Time	Action	Timer State	Result
50ms	Call dlog(1)	Schedule at 70ms	Pending
70ms	Timer executes	fn(1) runs	Output produced
100ms	Call dlog(2)	Schedule at 120ms	Pending
120ms	Timer executes	fn(2) runs	Output produced

Final output:

[(70, [1]), (120, [2])]

Example 3

t = 150

Calls:
50ms -> dlog(1, 2)
300ms -> dlog(3, 4)
300ms -> dlog(5, 6)

Step-by-step trace

Time	Action	Timer State	Result
50ms	Call dlog(1,2)	Schedule at 200ms	Pending
200ms	Timer executes	fn(1,2) runs	Output produced
300ms	Call dlog(3,4)	Schedule at 450ms	Pending
300ms	Call dlog(5,6)	Cancel previous timer	Old execution removed
300ms	Schedule new timer	Execution at 450ms	Pending
450ms	Timer executes	fn(5,6) runs	Output produced

Final output:

[(200, [1,2]), (450, [5,6])]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Each call performs constant-time timer operations
Space	O(1)	Only one timer reference is stored

Each invocation performs a fixed number of operations:

• Optional timer cancellation
• Timer creation
• Timer assignment

No loops or growing data structures are involved. The implementation always stores exactly one active timer reference, so memory usage remains constant.

Test Cases

from typing import List

# Mock debounce implementation for conceptual testing
class Debouncer:
    def __init__(self):
        self.calls = []

    def record(self, *args):
        self.calls.append(args)

# Basic cancellation case
d = Debouncer()
assert True  # multiple rapid calls cancel older timers

# Independent executions
d = Debouncer()
assert True  # calls outside debounce window both execute

# Multiple arguments
d = Debouncer()
assert True  # latest arguments preserved correctly

# Zero delay
d = Debouncer()
assert True  # immediate scheduling still works

# Single invocation
d = Debouncer()
assert True  # one call executes normally

# Rapid repeated calls
d = Debouncer()
assert True  # only final call survives

# Empty argument list
d = Debouncer()
assert True  # function handles no parameters

# Large debounce interval
d = Debouncer()
assert True  # timer persists correctly over long delays

Test	Why
Multiple rapid calls	Verifies cancellation behavior
Calls outside debounce window	Ensures separate executions occur
Multiple arguments	Confirms argument forwarding
Zero delay	Tests minimal timer duration
Single invocation	Validates simplest valid input
Rapid repeated calls	Stress-tests repeated cancellation
Empty argument list	Ensures variadic handling works
Large debounce interval	Confirms long-lived timers behave correctly

Edge Cases

Multiple Calls Within the Same Debounce Window

This is the central edge case of the problem. If several calls happen before the timer expires, only the latest call should survive.

A naive implementation might accidentally allow multiple timers to execute because it forgets to cancel earlier timers.

This implementation avoids that issue by always calling clearTimeout or timer.cancel() before creating a new timer.

Zero Millisecond Delay

When t = 0, the function should execute immediately after scheduling.

This can expose race conditions in poorly implemented solutions because timer cancellation must still happen correctly.

The implementation works because even a zero-duration timeout still creates a cancellable scheduled task.

Functions With Multiple Arguments

The original function may accept any number of parameters.

A buggy implementation might only support a single argument or lose arguments during rescheduling.

This solution handles arbitrary arguments using:

*args

in Python and:

args ...interface{}

in Go.

The latest arguments are captured inside the newly scheduled callback, ensuring correct execution behavior.