LeetCode Problem Workspace
Function Composition
Learn how to implement function composition by combining multiple functions into a single callable operation efficiently in JavaScript.
0
Topics
1
Code langs
0
Related
Practice Focus
Easy · Function Composition core interview pattern
Answer-first summary
Learn how to implement function composition by combining multiple functions into a single callable operation efficiently in JavaScript.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Function Composition core interview pattern
To solve Function Composition, start by returning a function that accepts a single integer input. Apply the array of functions from right to left, ensuring each output becomes the next function's input. Handle the edge case of an empty array by returning the input unchanged, reflecting the identity function behavior.
Problem Statement
Given an array of functions [f1, f2, ..., fn], implement a function that returns a new function representing their composition. The composed function should apply each function from right to left on an input integer.
If the input array is empty, the composed function should behave as the identity function, returning its input. Each function in the array accepts and returns a single integer, and the input x is guaranteed to be between -1000 and 1000.
Examples
Example 1
Input: functions = [x => x + 1, x => x * x, x => 2 * x], x = 4
Output: 65
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
Evaluating from right to left ... 10 * (1) = 10 10 * (10) = 100 10 * (100) = 1000
Example 3
Input: functions = [], x = 42
Output: 42
The composition of zero functions is the identity function
Constraints
- -1000 <= x <= 1000
- 0 <= functions.length <= 1000
- all functions accept and return a single integer
Solution Approach
Return a wrapper function
Start by returning a new function that takes an integer x. This ensures that the composition can be called with any valid integer input and supports chaining the inner functions.
Iterate from right to left
Apply each function in the array starting from the last element to the first. Pass the result of each function as input to the previous one. This maintains the correct order of function composition.
Handle empty arrays
If the functions array is empty, return x immediately. This respects the identity function requirement and prevents errors from trying to iterate over an empty array.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) per function call where n is the number of functions, since each function is applied once. Space complexity is O(1) additional space if implemented iteratively, or O(n) if using recursion due to call stack.
What Interviewers Usually Probe
- Look for correct right-to-left application of functions.
- Check if the candidate handles empty arrays as identity functions.
- Verify that each function is called exactly once in order.
Common Pitfalls or Variants
Common pitfalls
- Applying functions from left to right instead of right to left.
- Not returning a function, which breaks the composition pattern.
- Failing to handle empty arrays, causing runtime errors.
Follow-up variants
- Compose functions that accept multiple arguments instead of a single integer.
- Compose asynchronous functions returning promises for functional chaining.
- Optimize composition by reducing repeated calls for idempotent functions.
FAQ
What is Function Composition in this LeetCode problem?
Function Composition requires combining an array of single-argument functions into one function that applies them from right to left.
How do I handle an empty functions array?
Return a function that simply returns its input, acting as the identity function.
Do I need to worry about the input range?
Yes, all inputs x are integers between -1000 and 1000, and each function returns a valid integer.
Can I use recursion for composition?
Yes, recursion works but watch the call stack size; iterative solutions are often safer for large arrays.
Why is right-to-left function application important?
The problem specifically defines composition as fn(x) = f(g(h(x))), so reversing the order produces correct outputs.
Solution
Solution 1
#### TypeScript
type F = (x: number) => number;
function compose(functions: F[]): F {
return function (x) {
return functions.reduceRight((acc, fn) => fn(acc), x);
};
}
/**
* const fn = compose([x => x + 1, x => 2 * x])
* fn(4) // 9
*/