Function Composition - Solution & Explanation
Problem Statement
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 <= 1000- all functions accept and return a single integer
Approach Overview
Problem 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 1: Iterative Right-to-Left Composition
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.
Complexity
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.
Approach 2: Recursive Right-to-Left Composition
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.
Complexity
Time Complexity: O(n) where n is the number of functions.
Space Complexity: O(n) due to the recursive call stack.
Approach 3: Default Approach
Code
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Function Composition - Leetcode 2629 - JavaScript 30-Day Challenge • NeetCodeIO • 19,231 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Function Composition easy or hard?
Function Composition Python/Java solution
How to solve Function Composition in O(n)?
What is the best approach for Function Composition?
Is Function Composition asked at Google/Amazon/Meta?
What data structure is used in Function Composition?
What is the time complexity of Function Composition?
Ready to solve this problem?
Practice Function Composition with our built-in code editor and test cases.
Practice on FleetCode