LeetCode 2636 - Promise Pool

LeetCode Problem 2636

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to implement a concurrency limiter for asynchronous operations.

We are given an array called functions, where each element is itself a function. When one of these functions is called, it returns a Promise. Each Promise represents some asynchronous work, such as waiting for a timeout or making a network request.

We are also given an integer n, which represents the maximum number of Promises that are allowed to be running at the same time. This is called the pool limit.

The goal is to create a function named promisePool that executes the asynchronous functions while respecting this concurrency limit.

The important detail is that we should always try to keep the pool as full as possible. If fewer than n Promises are currently running and there are still functions left to execute, we should immediately start another one.

The execution order matters. We must begin with functions[0], then functions[1], then functions[2], and so on. However, the completion order does not necessarily match the execution order because different Promises may take different amounts of time to resolve.

The returned Promise should resolve only after every input function has completed.

For example:

• If n = 1, only one Promise may run at a time, so the functions execute sequentially.
• If n = 2, two Promises can run simultaneously.
• If n is larger than the number of functions, then all functions can start immediately.

The constraints are very small:

• 0 <= functions.length <= 10
• 1 <= n <= 10

This means performance is not a major issue for the actual input size, but the problem is designed to test understanding of asynchronous control flow and concurrency management.

Several edge cases are important:

• The input array may be empty.
• n may be larger than the number of functions.
• n may equal 1, forcing strictly sequential execution.
• Multiple Promises may resolve at nearly the same time.
• The problem guarantees that Promises never reject, so we do not need error handling logic.

Approaches

Brute Force Approach

The most straightforward solution is to execute the functions sequentially.

We could iterate through the array and await each Promise before starting the next one. This guarantees correctness because only one Promise is active at a time, so the pool limit is never exceeded.

However, this approach completely ignores the concurrency limit when n > 1. Even if multiple Promises are allowed to run simultaneously, we still execute them one by one.

For example, if three tasks each take 1 second and n = 3, the sequential solution would still take 3 seconds instead of 1 second.

This solution is correct but inefficient because it does not utilize available concurrency.

Optimal Approach

The key insight is that we should always maintain up to n active Promises whenever possible.

Instead of waiting for all currently running tasks to finish, we can start a new task immediately whenever one task completes.

A common way to implement this is:

1. Keep track of the next function index to execute.
2. Start up to n worker coroutines.
3. Each worker repeatedly:

• Takes the next available function index.
• Executes that function.
• Waits for it to finish.
• Repeats until no functions remain.

This creates a dynamic scheduling system where completed workers automatically pick up new work.

The important observation is that at most n workers exist simultaneously, so at most n Promises are active at once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m)	O(1)	Executes every Promise sequentially
Optimal	O(m)	O(n)	Maintains up to n concurrent Promises

Here, m represents the number of functions.

Algorithm Walkthrough

1. First, create a shared variable called next_index that tracks the next function that has not yet been started.
2. Define an asynchronous worker function. This worker is responsible for repeatedly pulling tasks from the shared queue.
3. Inside the worker:

• Check whether next_index is still within bounds.
• If not, there is no work left, so return.
• Otherwise, store the current index and increment next_index.

4. Execute the function at that index by calling await functions[current_index]().
5. After the Promise resolves, loop back and try to acquire another task.
6. Create up to n workers. If there are fewer functions than n, only create as many workers as necessary.
7. Use await asyncio.gather(...) in Python, or a sync.WaitGroup in Go, to wait until all workers finish.
8. Once all workers complete, all Promises have resolved, so the pool function can resolve as well.

Why it works

The algorithm maintains the invariant that each function index is assigned exactly once.

Because all workers share the same next_index, every task is uniquely claimed before execution. Since there are at most n workers running concurrently, the number of active Promises never exceeds the pool limit.

Whenever a worker finishes a Promise, it immediately attempts to start another task, which keeps the pool utilized as efficiently as possible.

Python Solution

from typing import List, Callable, Awaitable
import asyncio

class Solution:
    async def promisePool(
        self,
        functions: List[Callable[[], Awaitable[None]]],
        n: int
    ) -> None:
        next_index = 0

        async def worker() -> None:
            nonlocal next_index

            while True:
                if next_index >= len(functions):
                    return

                current_index = next_index
                next_index += 1

                await functions[current_index]()

        worker_count = min(n, len(functions))

        await asyncio.gather(
            *(worker() for _ in range(worker_count))
        )

The implementation begins by defining next_index, which acts as a shared pointer to the next unprocessed function.

The nested worker coroutine repeatedly pulls work from the shared index. Each worker claims one task by storing the current index and incrementing next_index.

After claiming a task, the worker executes the asynchronous function using await.

The while True loop allows each worker to continue processing tasks until none remain.

We create at most n workers because the pool limit defines the maximum concurrency. If there are fewer functions than workers, we only create enough workers for the available tasks.

Finally, asyncio.gather waits for all workers to finish before resolving the pool.

Go Solution

package main

import "sync"

type AsyncFunc func() chan struct{}

func promisePool(functions []AsyncFunc, n int) chan struct{} {
	done := make(chan struct{})

	go func() {
		defer close(done)

		var mutex sync.Mutex
		nextIndex := 0

		var wg sync.WaitGroup

		worker := func() {
			defer wg.Done()

			for {
				mutex.Lock()

				if nextIndex >= len(functions) {
					mutex.Unlock()
					return
				}

				currentIndex := nextIndex
				nextIndex++

				mutex.Unlock()

				<-functions[currentIndex]()
			}
		}

		workerCount := n
		if len(functions) < workerCount {
			workerCount = len(functions)
		}

		wg.Add(workerCount)

		for i := 0; i < workerCount; i++ {
			go worker()
		}

		wg.Wait()
	}()

	return done
}

The Go version uses goroutines instead of Python coroutines.

A sync.Mutex protects access to nextIndex because multiple workers may attempt to claim tasks simultaneously.

A sync.WaitGroup tracks active workers and allows the main goroutine to wait until all workers finish.

The asynchronous functions are represented as functions returning channels. Waiting on <-functions[currentIndex]() simulates awaiting a Promise.

Unlike Python, Go requires explicit synchronization primitives because goroutines execute concurrently at the system level.

Worked Examples

Example 1

Input:

functions = [300ms, 400ms, 200ms]
n = 2

Initial state:

Time	Active Tasks	Next Index
0	[]	0

Start first two workers.

Time	Active Tasks	Next Index
0	[300, 400]	2

At 300ms, the first task finishes.

Worker immediately starts the third task.

Time	Active Tasks	Next Index
300	[400, 200]	3

At 400ms, the second task finishes.

Time	Active Tasks	Next Index
400	[200]	3

At 500ms, the third task finishes.

Time	Active Tasks	Next Index
500	[]	3

All tasks are complete, so the pool resolves at 500ms.

Example 2

Input:

functions = [300ms, 400ms, 200ms]
n = 5

Since n exceeds the number of functions, all tasks start immediately.

Time	Active Tasks
0	[300, 400, 200]

Completion order:

Time	Finished Task
200	200ms task
300	300ms task
400	400ms task

The pool resolves at 400ms.

Example 3

Input:

functions = [300ms, 400ms, 200ms]
n = 1

Only one task may run at a time.

Time	Active Task
0	300

At 300ms, start the second task.

Time	Active Task
300	400

At 700ms, start the third task.

Time	Active Task
700	200

At 900ms, all work completes.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m)	Each function is executed exactly once
Space	O(n)	At most n workers exist simultaneously

The algorithm processes every function exactly once, so the total work is linear in the number of tasks.

The additional memory comes primarily from the active worker coroutines or goroutines. Since at most n workers exist simultaneously, the auxiliary space usage is proportional to the pool size.

Test Cases

import asyncio

class Solution:
    async def promisePool(self, functions, n):
        next_index = 0

        async def worker():
            nonlocal next_index

            while True:
                if next_index >= len(functions):
                    return

                current = next_index
                next_index += 1

                await functions[current]()

        await asyncio.gather(
            *(worker() for _ in range(min(n, len(functions))))
        )

async def run_tests():
    sol = Solution()

    # Empty input
    await sol.promisePool([], 3)

    # Single task
    result = []

    async def task1():
        result.append(1)

    await sol.promisePool([task1], 1)
    assert result == [1]  # Single function execution

    # Sequential execution with n = 1
    order = []

    async def a():
        order.append("a")

    async def b():
        order.append("b")

    async def c():
        order.append("c")

    await sol.promisePool([a, b, c], 1)
    assert order == ["a", "b", "c"]  # Sequential ordering

    # More workers than tasks
    result = []

    async def x():
        result.append("x")

    async def y():
        result.append("y")

    await sol.promisePool([x, y], 10)
    assert sorted(result) == ["x", "y"]  # All tasks still execute

    # Multiple concurrent tasks
    counter = 0

    async def increment():
        nonlocal counter
        counter += 1

    await sol.promisePool([increment for _ in range(5)], 2)
    assert counter == 5  # Every task executed exactly once

asyncio.run(run_tests())

Test	Why
Empty input	Ensures no workers are created unnecessarily
Single task	Validates minimal non-empty case
n = 1	Confirms sequential execution
n > len(functions)	Ensures all tasks start immediately
Multiple concurrent tasks	Verifies every task executes exactly once

Edge Cases

Empty Function Array

If functions is empty, there is nothing to execute. A naive implementation might still attempt to create workers or access invalid indices.

This implementation handles the case correctly because worker_count becomes 0, so asyncio.gather receives no workers and immediately resolves.

Pool Size Larger Than Number of Tasks

If n exceeds the number of functions, we should not create unnecessary workers.

For example:

functions.length = 2
n = 10

Only two workers are needed because there are only two tasks available. The implementation correctly uses:

min(n, len(functions))

to avoid redundant workers.

Sequential Execution with n = 1

This case effectively turns the pool into a queue.

A common bug is accidentally starting multiple tasks before awaiting completion. In this implementation, only one worker exists when n = 1, so tasks execute strictly one after another.

Simultaneous Promise Resolution

Multiple Promises may finish at nearly the same time. Without careful task assignment, two workers could accidentally execute the same function index.

The implementation prevents this by incrementing next_index immediately when a worker claims a task. Each task index is therefore assigned exactly once.