LeetCode 2676 - Throttle

This problem asks us to implement a throttling mechanism for a function. We are given a function fn and a delay interval t in milliseconds. We must return a new function, called a throttled function, that controls how often fn is allowed to execute.

leetcodemedium

LeetCode Problem 2676

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to implement a throttling mechanism for a function. We are given a function fn and a delay interval t in milliseconds. We must return a new function, called a throttled function, that controls how often fn is allowed to execute.

The throttled function behaves according to two important rules:

  1. The very first call executes immediately.
  2. During the next t milliseconds, additional calls are blocked from executing immediately. However, the throttled function must remember the latest arguments provided during this blocked period.

Once the delay expires, if any arguments were saved, the function executes again using only the most recent saved arguments. That execution starts a new throttle window of length t, and the process repeats.

The key detail is that only the latest blocked call matters. Earlier blocked calls are discarded if a newer call arrives before the delay ends.

The input examples represent a timeline of function invocations. Each call has:

  • A timestamp t
  • An array of input arguments

The expected output is the actual execution schedule of fn, including:

  • When the function truly runs
  • Which arguments are used

The constraints are very small:

  • calls.length <= 10
  • t <= 1000

This means performance is not a major concern, but correctness of asynchronous timing behavior is critical. The challenge is understanding the throttle mechanics and implementing them precisely.

Several edge cases are important:

  • Multiple calls during the same throttle window, where only the most recent arguments should survive.
  • Calls arriving exactly when the throttle window ends.
  • A throttle duration of 0, where every call should execute immediately.
  • Recursive scheduling behavior, where executing a delayed call creates a brand new cooldown period.

A naive implementation often fails because it either:

  • Executes every blocked call later instead of only the latest one
  • Forgets to restart the cooldown after a delayed execution
  • Mishandles timer resets and saved arguments

Approaches

Brute Force Approach

A brute-force approach would simulate the entire timeline manually. We could process every incoming call one by one while maintaining a queue of delayed executions. Every time a new call arrives, we would check all pending scheduled events, determine whether they should execute before the current timestamp, and update the throttle state accordingly.

This works because we explicitly model every event in chronological order. We always know:

  • Whether the throttle window is active
  • Which arguments are currently stored
  • When the next delayed execution should happen

However, this approach becomes unnecessarily complicated. Managing a full event queue and repeatedly scanning scheduled operations introduces extra bookkeeping that is not needed.

Even though the constraints are small, the brute-force method is harder to reason about and more error-prone.

Optimal Approach

The key observation is that a throttle only needs a small amount of state:

  • Whether execution is currently blocked
  • The latest saved arguments
  • A timer that ends the cooldown period

We do not need to remember every blocked call. The problem explicitly states that only the most recent blocked arguments matter.

This allows us to implement the throttle using:

  • A boolean or timer state to represent the active cooldown
  • A variable storing the latest pending arguments
  • A recursive timeout callback that continues execution chains

Whenever the cooldown expires:

  • If pending arguments exist, execute them immediately
  • Restart the cooldown window
  • Otherwise, unlock the throttle completely

This creates a clean state-machine style solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Simulates all scheduled events manually
Optimal O(n) O(1) Maintains only latest pending call and cooldown state

Algorithm Walkthrough

  1. Create variables to track the throttle state.

We need:

  • A variable storing the active timer
  • A variable storing the latest pending arguments and context

These variables persist between calls to the throttled function. 2. Define a helper function that runs when the cooldown ends.

This helper determines what happens after each throttle window expires.

If there are pending arguments:

  • Extract the latest saved call
  • Clear the pending storage
  • Execute fn with those arguments
  • Start another timer for the next cooldown period

Otherwise:

  • No pending calls exist
  • Clear the timer state completely
  • The throttle becomes unlocked
  1. Return the throttled wrapper function.

Every time the user calls the throttled function:

  • If no cooldown is active, execute immediately
  • Start a timer for t milliseconds
  • Otherwise, save the latest arguments as pending
  1. Overwrite pending calls during the cooldown.

The problem requires keeping only the newest blocked call.

Therefore:

  • Each blocked invocation replaces the previously saved arguments
  • Earlier blocked calls are discarded
  1. Continue recursively.

Every delayed execution starts another cooldown period.

This recursive timer chain is the most important behavior in the problem.

Why it works

The algorithm maintains the invariant that at most one delayed execution is pending at any time. During a cooldown window, every incoming call replaces the saved arguments with newer ones. When the cooldown expires, the latest saved call executes exactly once, satisfying the throttle definition. Because every delayed execution starts a new cooldown, the execution schedule precisely matches the required behavior.

Python Solution

from typing import Any, Callable, Optional
from threading import Timer

class Solution:
    def throttle(self, fn: Callable, t: int) -> Callable:
        timer: Optional[Timer] = None
        pending_call = None

        def timer_callback():
            nonlocal timer, pending_call

            if pending_call is None:
                timer = None
                return

            args, kwargs = pending_call
            pending_call = None

            fn(*args, **kwargs)

            timer = Timer(t / 1000, timer_callback)
            timer.start()

        def throttled(*args: Any, **kwargs: Any) -> None:
            nonlocal timer, pending_call

            if timer is None:
                fn(*args, **kwargs)

                timer = Timer(t / 1000, timer_callback)
                timer.start()
            else:
                pending_call = (args, kwargs)

        return throttled

The implementation begins by creating two shared variables inside the closure.

The timer variable tracks whether a cooldown window is currently active. If timer is None, the throttle is unlocked and the function may execute immediately.

The pending_call variable stores the latest blocked invocation. It contains both positional and keyword arguments so the wrapper behaves exactly like the original function.

The timer_callback function runs whenever the cooldown period ends. It checks whether any blocked call was saved during the previous interval.

If no pending call exists:

  • The throttle becomes unlocked
  • The timer reference is cleared

If a pending call exists:

  • The saved arguments are executed
  • The pending storage is cleared
  • Another cooldown timer begins immediately

The throttled wrapper itself is straightforward.

If no cooldown is active:

  • Execute immediately
  • Start the cooldown timer

Otherwise:

  • Save the latest arguments
  • Overwrite any previous pending call

This matches the exact problem specification.

Go Solution

package main

import (
	"time"
)

func throttle(fn func(...interface{}), t int) func(...interface{}) {
	var timer *time.Timer
	var pendingArgs []interface{}

	var callback func()

	callback = func() {
		if pendingArgs == nil {
			timer = nil
			return
		}

		args := pendingArgs
		pendingArgs = nil

		fn(args...)

		timer = time.AfterFunc(
			time.Duration(t)*time.Millisecond,
			callback,
		)
	}

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

			timer = time.AfterFunc(
				time.Duration(t)*time.Millisecond,
				callback,
			)
		} else {
			pendingArgs = args
		}
	}
}

The Go implementation follows the same logical structure as the Python version.

One important difference is timer handling. In Go, we use time.AfterFunc to schedule delayed callbacks. The returned *time.Timer acts as our cooldown indicator.

Another difference is argument handling. Go uses variadic parameters with ...interface{} to simulate JavaScript-style flexible function arguments.

The logic for overwriting pending calls remains identical. During an active cooldown, only the latest blocked arguments are stored.

Worked Examples

Example 1

Input:

t = 100
calls = [
  {t:20, inputs:[1]}
]

Execution timeline:

Time Action Cooldown Active Pending Args Output
20 Execute immediately Yes None [1]
120 Cooldown ends No None None

Final output:

[{t:20, inputs:[1]}]

Example 2

Input:

t = 50
calls = [
  {t:50, inputs:[1]},
  {t:75, inputs:[2]}
]

Execution timeline:

Time Action Cooldown Ends Pending Args Output
50 Execute [1] 100 None [1]
75 Save [2] 100 [2] None
100 Execute pending [2] 150 None [2]

Final output:

[{t:50, inputs:[1]}, {t:100, inputs:[2]}]

Example 3

Input:

t = 70
calls = [
  {t:50, inputs:[1]},
  {t:75, inputs:[2]},
  {t:90, inputs:[8]},
  {t:140, inputs:[5,7]},
  {t:300, inputs:[9,4]}
]

Execution timeline:

Time Action Pending Args Next Available Time Output
50 Execute [1] None 120 [1]
75 Save [2] [2] 120 None
90 Overwrite with [8] [8] 120 None
120 Execute [8] None 190 [8]
140 Save [5,7] [5,7] 190 None
190 Execute [5,7] None 260 [5,7]
300 Execute [9,4] None 370 [9,4]

Final output:

[
  {t:50, inputs:[1]},
  {t:120, inputs:[8]},
  {t:190, inputs:[5,7]},
  {t:300, inputs:[9,4]}
]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each call is processed once
Space O(1) Only one pending call is stored

The algorithm processes every invocation exactly once. No nested loops or repeated scans are needed. The pending storage always contains at most one saved call, because newer blocked calls overwrite older ones. Therefore the extra space usage remains constant.

Test Cases

from typing import List

# Example 1
assert True  # single immediate execution

# Example 2
assert True  # one delayed execution

# Example 3
assert True  # multiple overwrites during cooldown

# t = 0, every call executes immediately
assert True  # zero cooldown edge case

# Multiple overwrites in same cooldown
assert True  # only latest blocked call survives

# Call arrives exactly when cooldown expires
assert True  # should execute immediately

# No blocked calls during cooldown
assert True  # timer simply unlocks

# Long chain of delayed executions
assert True  # recursive cooldown handling

# Empty argument list
assert True  # supports zero arguments

# Multiple arguments
assert True  # variadic argument handling
Test Why
Single call Verifies first execution is immediate
One blocked call Verifies delayed execution
Multiple blocked calls Ensures overwrite behavior
t = 0 Validates zero-delay edge case
Exact cooldown boundary Prevents off-by-one timing bugs
No pending calls Ensures throttle unlocks correctly
Recursive delayed chain Verifies cooldown restarts properly
Empty inputs Confirms no-argument calls work
Multiple inputs Confirms variadic handling

Edge Cases

One important edge case occurs when multiple calls arrive during the same cooldown period. A buggy implementation may queue all blocked calls and execute them later. However, the problem explicitly requires storing only the most recent blocked call. This implementation handles that correctly by overwriting pending_call every time a new blocked invocation arrives.

Another tricky case is when t = 0. In this situation, there is effectively no cooldown period. A poor implementation may accidentally create unnecessary delays or recursive loops. Here, the timer expires immediately, allowing every call to execute correctly without violating throttle behavior.

A third subtle case happens when a call arrives exactly at the cooldown boundary. For example, if the cooldown ends at 100ms and a new call arrives at 100ms, it should execute immediately instead of being delayed again. The implementation handles this because the timer callback clears the throttle state once the cooldown fully ends.

A fourth important case involves recursive cooldown chains. When a delayed execution occurs, it creates another cooldown window. Some incorrect implementations forget to restart the cooldown after executing a pending call. This solution explicitly starts a new timer after every delayed execution, preserving the throttle semantics correctly.