Function Composition

Difficulty: Easy | Acceptance: 86.80% | Paid: No Topics: N/A

Given an array of functions [f1, f2, …, fn], return a new function fn that is the function composition of the array of functions.

The function composition of [f(x), g(x), h(x)] is fn(x) = f(g(h(x))).

The function composition of an empty list of functions is the identity function f(x) = x.

• Examples
• Constraints
• Iterative Approach
• Recursive Approach
• Reduce Approach

Examples

Input: functions = [x => x + 1, x => x * x, x => 2 * x], x = 4
Output: 65
Explanation:
Evaluating from right to left ...
Starting with x = 4.
2 * (4) = 8
(8) * (8) = 64
(64) + 1 = 65

Input: functions = [x => 10 * x, x => 10 * x, x => 10 * x], x = 1
Output: 1000
Explanation:
Evaluating from right to left ...
10 * (1) = 10
10 * (10) = 100
10 * (100) = 1000

Input: functions = [], x = 42
Output: 42
Explanation:
The composition of zero functions is the identity function.

Constraints

- 0 <= functions.length <= 1000
- All functions accept and return a single integer
- The number of function calls will not exceed 1000

Iterative Approach

Intuition Start with the input value and apply each function from right to left, updating the result at each step.

Steps

• Initialize result with the input value x
• Iterate through functions array from right to left
• Apply each function to the current result
• Return the final result

from typing import List, Callable

def compose(functions: List[Callable[[int], int]]) -> Callable[[int], int]:
    def fn(x: int) -> int:
        result = x
        for f in reversed(functions):
            result = f(result)
        return result
    return fn

Complexity

• Time: O(n) where n is the number of functions
• Space: O(1) excluding the output function
• Notes: Simple and straightforward approach with clear logic

Recursive Approach

Intuition Use recursion to apply functions from right to left, with the base case being when all functions have been applied.

Steps

• Define a helper function that takes current value and index
• Base case: if index is negative, return the current value
• Recursive case: apply function at current index and recurse with index - 1
• Return a closure that calls the helper with the last index

from typing import List, Callable

def compose(functions: List[Callable[[int], int]]) -> Callable[[int], int]:
    def helper(x: int, index: int) -> int:
        if index < 0:
            return x
        return helper(functions[index](x), index - 1)
    
    return lambda x: helper(x, len(functions) - 1)

Complexity

• Time: O(n) where n is the number of functions
• Space: O(n) for the recursion stack
• Notes: Elegant but may cause stack overflow for very large function arrays

Reduce Approach

Intuition Use the reduce pattern to accumulate the result by applying each function from right to left.

Steps

• Use reduceRight (or reverse + reduce) to apply functions
• Start with the initial value x
• Each step applies the current function to the accumulated result
• Return the final composed function

from typing import List, Callable
from functools import reduce

def compose(functions: List[Callable[[int], int]]) -> Callable[[int], int]:
    return lambda x: reduce(lambda acc, f: f(acc), reversed(functions), x)

Complexity

• Time: O(n) where n is the number of functions
• Space: O(1) excluding the output function
• Notes: Most idiomatic functional programming approach, concise and readable