Given an array of functions [f1, f2, f3, ..., 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.
You may assume each function in the array accepts one integer as input and returns one integer as output.
Example 1:
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
Example 2:
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
Example 3:
Input: functions = [], x = 42 Output: 42 Explanation: The composition of zero functions is the identity function
Constraints:
-1000 <= x <= 10000 <= functions.length <= 1000Problem Overview: You receive an array of functions and must return a single function representing their composition. When the returned function is called with value x, it should apply the functions from right to left, meaning the last function runs first and its result flows through the remaining functions.
Approach 1: Iterative Right-to-Left Composition (O(n) time, O(1) space)
Store the input value in a variable and iterate through the function array from the last index to the first. At each step, call the current function using the running value and overwrite the result. This mirrors mathematical function composition: f(g(h(x))). The key idea is that the output of one function becomes the input of the next as you move left in the array. Time complexity is O(n) per invocation of the composed function because each function is executed exactly once, while auxiliary space stays O(1) since only a single variable stores intermediate results. This approach is straightforward and avoids recursion overhead.
Approach 2: Recursive Right-to-Left Composition (O(n) time, O(n) space)
Recursion models composition naturally. Start from the last function and recursively apply the remaining functions until reaching the first. Each recursive call passes the result of the current function to the previous one. Conceptually, this builds a call stack similar to nested expressions like f(g(h(x))). The total runtime remains O(n) because each function executes once. However, recursion introduces O(n) space complexity due to the call stack. This style is common when working with recursion or functional pipelines, but many engineers prefer the iterative approach for clarity and stack safety.
Both solutions rely on simple traversal of the array of functions. The composition concept itself comes from functional programming, where functions are treated as first-class values and combined to build pipelines.
Recommended for interviews: The iterative right-to-left approach. It clearly demonstrates understanding of function composition while keeping space usage constant. The recursive version shows conceptual clarity but adds unnecessary stack overhead for this problem.
Iterative Approach: In this approach, we compose the functions iteratively from the last function to the first. This is because function composition works in reverse order, i.e., f(g(h(x))) means first apply h, then g, and finally f. We start with the input value x and apply each function in the function list from right to left.
This C solution defines an array of function pointers and iterates over the functions from right to left, applying each one to the initial input. Each function is applied in turn, modifying the input, and the final result is returned.
Time Complexity: O(n) where n is the number of functions.
Space Complexity: O(1) since we are using a fixed amount of extra space.
Recursive Approach: This approach encapsulates the recursive function composition in a way that it applies the last function first and makes a recursive call to apply the rest. We either call the next composed function recursively until the base case, i.e., no functions left, is reached, or upon an empty function list, return the input as it is simply the identity function.
This C implementation defines a recursive function which applies the last function in the array and then calls itself with the remaining functions one less in length, composed into a single final result.
Time Complexity: O(n) where n is the number of functions.
Space Complexity: O(n) due to the recursive call stack.
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Right-to-Left Composition | Time Complexity: O(n) where n is the number of functions. |
| Recursive Right-to-Left Composition | Time Complexity: O(n) where n is the number of functions. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Right-to-Left Composition | O(n) | O(1) | Best general solution; avoids recursion overhead and processes each function once |
| Recursive Right-to-Left Composition | O(n) | O(n) | Useful for demonstrating recursive composition patterns or functional-style implementations |
Function Composition - Leetcode 2629 - JavaScript 30-Day Challenge • NeetCodeIO • 18,807 views views
Watch 9 more video solutions →Practice Function Composition with our built-in code editor and test cases.
Practice on FleetCode