LeetCode 2637 - Promise Time Limit

LeetCode Problem 2637

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to implement a time-limited wrapper around an asynchronous function. We are given an input function fn that returns a Promise and a time limit t in milliseconds. The task is to return a new function that executes fn but enforces a maximum execution time. If fn resolves before t milliseconds, the wrapper should resolve with the same value. If fn takes longer than t milliseconds, the wrapper should reject with "Time Limit Exceeded".

The input fn can take any number of arguments (inputs array), and it may either resolve or reject. The time limit t can be zero, meaning the function should immediately reject if the execution does not complete instantly. The constraints are small, with at most 10 arguments and a maximum time limit of 1000 milliseconds, so performance is not a huge concern.

Important edge cases include fn throwing immediately, fn resolving exactly at the boundary of t, t = 0, and fn being called with no arguments. The problem guarantees that fn always returns a Promise, so we do not need to handle synchronous return values directly.

Approaches

The naive approach would be to repeatedly poll the Promise or set timeouts manually inside fn to check whether it resolves in time. This would work but is cumbersome, error-prone, and unnecessarily complicated. It also does not leverage the native concurrency mechanisms of Promises.

The optimal approach is to use Promise.race. This built-in method allows us to run two promises concurrently and resolves or rejects with whichever finishes first. We can race the original fn Promise against a timeout Promise that rejects after t milliseconds. This gives a concise and robust solution without manually tracking elapsed time or repeatedly checking.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Manually poll or track elapsed time to enforce timeout, verbose and error-prone
Optimal	O(1)	O(1)	Use Promise.race to run fn and timeout concurrently, resolves correctly in all cases

Algorithm Walkthrough

1. Define a new function limitedFn that takes the same arguments as fn.
2. Inside limitedFn, create a timeout promise that rejects with "Time Limit Exceeded" after t milliseconds. This can be done using setTimeout.
3. Call the original fn with the provided arguments. This returns a Promise that resolves or rejects normally.
4. Use Promise.race to run the original function's Promise and the timeout Promise concurrently. Whichever settles first determines the result.
5. Return the result of Promise.race as the result of limitedFn.
6. Handle all resolutions and rejections normally; no additional logic is needed since Promise.race ensures only the first settling Promise matters.

Why it works: The key invariant is that Promise.race guarantees the first settling Promise is used. By creating a timeout Promise that rejects after exactly t milliseconds, we ensure that any function taking longer than t is automatically rejected. Functions that resolve faster succeed, so all requirements are satisfied.

Python Solution

from typing import Any, Callable
import asyncio

def timeLimit(fn: Callable[..., asyncio.Future], t: int) -> Callable[..., asyncio.Future]:
    async def limited_fn(*args: Any) -> Any:
        timeout_task = asyncio.create_task(asyncio.sleep(t / 1000))
        func_task = asyncio.create_task(fn(*args))
        done, pending = await asyncio.wait(
            {timeout_task, func_task}, return_when=asyncio.FIRST_COMPLETED
        )
        for task in pending:
            task.cancel()
        if func_task in done:
            return await func_task
        else:
            raise Exception("Time Limit Exceeded")
    return limited_fn

The implementation first converts the timeout t to seconds because asyncio.sleep expects seconds. Both the function call and the timeout are wrapped in tasks and passed to asyncio.wait with FIRST_COMPLETED. Once one finishes, the other is canceled. If the function finished first, we await its result. Otherwise, we raise a "Time Limit Exceeded" exception.

Go Solution

package main

import (
    "errors"
    "time"
)

func TimeLimit(fn func(...any) (any, error), t int) func(...any) (any, error) {
    return func(args ...any) (any, error) {
        result := make(chan any, 1)
        errChan := make(chan error, 1)

        go func() {
            res, err := fn(args...)
            if err != nil {
                errChan <- err
            } else {
                result <- res
            }
        }()

        select {
        case res := <-result:
            return res, nil
        case err := <-errChan:
            return nil, err
        case <-time.After(time.Duration(t) * time.Millisecond):
            return nil, errors.New("Time Limit Exceeded")
        }
    }
}

In Go, channels are used to collect the function result or error. A select statement waits for the function result, an error, or a timeout. The timeout is enforced with time.After. This handles all edge cases without needing additional synchronization primitives.

Worked Examples

Example 1:

fn resolves after 100ms, time limit 50ms. The timeout Promise rejects first, so the output is {"rejected":"Time Limit Exceeded","time":50}.

Example 2:

fn resolves after 100ms, time limit 150ms. The function Promise resolves first, so the output is {"resolved":25,"time":100}.

Example 3:

fn resolves after 120ms, time limit 150ms. The function Promise resolves first, output is {"resolved":15,"time":120}.

Example 4:

fn immediately throws. The function Promise rejects immediately, so output is {"rejected":"Error","time":0}.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Both Python asyncio and Go select run concurrently; only one result is needed. Timeout does not add loops.
Space	O(1)	Only two Promises/tasks (or channels in Go) are created, regardless of input size.

The time and space are constant relative to the input because we only track two concurrent operations, and the input argument length is capped at 10.

Test Cases

import asyncio

async def test():
    async def fn1(n):
        await asyncio.sleep(0.1)
        return n * n

    async def fn2(a, b):
        await asyncio.sleep(0.12)
        return a + b

    async def fn3():
        raise Exception("Error")

    limited1 = timeLimit(fn1, 50)
    try:
        await limited1(5)
    except Exception as e:
        assert str(e) == "Time Limit Exceeded"  # Timeout triggered

    limited2 = timeLimit(fn1, 150)
    assert await limited2(5) == 25  # Resolved normally

    limited3 = timeLimit(fn2, 150)
    assert await limited3(5, 10) == 15  # Resolved normally

    limited4 = timeLimit(fn3, 1000)
    try:
        await limited4()
    except Exception as e:
        assert str(e) == "Error"  # Immediate rejection

    limited5 = timeLimit(fn1, 0)
    try:
        await limited5(5)
    except Exception as e:
        assert str(e) == "Time Limit Exceeded"  # Zero timeout edge case

asyncio.run(test())

Test	Why
fn resolves slower than t	Ensures timeout triggers correctly
fn resolves faster than t	Ensures normal resolution works
fn rejects immediately	Ensures immediate error is handled
t = 0	Ensures boundary timeout is handled correctly

Edge Cases

One important edge case is when t = 0. In this case, the function should almost always reject because even the fastest function call will take some microseconds. Our implementation converts t to milliseconds and schedules a timeout accordingly, so this is handled.

Another edge case is when fn immediately throws an exception. A naive implementation that only checks elapsed time might not propagate this error. By racing the function promise with a timeout promise, immediate rejection is correctly returned.

Finally, fn resolving exactly at the timeout boundary is subtle. The race guarantees that if the function resolves first, even by 1 millisecond, the result is returned. If the timeout Promise fires first, rejection occurs. This ensures strict enforcement of the time limit without ambiguity.