Watch 10 video solutions for Function Composition, a easy level problem. This walkthrough by NeetCodeIO has 18,807 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |