Function Composition solution and explanation
Google
9 more videos on this problem
Function Composition - Leetcode 2629 - JavaScript 30-Day ChallengeNeetCodeIO · 8:09 · 19K views
Function Composition | Leetcode 2629 | Function Transformations | 30 Days of JavaScript #leetcodeLearn With Chirag · 18:16 · 4K views
2629. Function Composition - Leetcode JavaScript Solution with ExplanationEndeavour Monk · 9:51 · 1K views
Leetcode javascript Day-7 || 2629. Function CompositionAnshulOnTech · 5:53 · 1K views
#day8 | 2629. Function Composition | 30 Days of Javascript | Leetcode-2629 | 30 Days ChallengeCoding with Ankita · 17:31 · 712 views
2629. Function Composition - Day 7/30 Leetcode Javascript ChallengeProgramming Live with Larry · 2:29 · 527 views
2629. Function Composition😎 || Leetcode 30 Days JavaScript Challenge🔥 || FunctionsPhoenix Code Lover · 1:45 · 242 views
Leetcode 2629 || Function Composition || Recursive Solution || JavascriptDev Smasher · 6:48 · 189 views
Function Composition - LeetCode 2629 - JavaScript - JS 30 Day Challenge Day 7Alpha-Code · 7:12 · 179 views
Functional JavaScript: 2629 - Function Composition in Depth | Day 7 of 30-Day Leetcode ChallengevanAmsen · 6:11 · 160 views
The problem
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.
from typing import List, Callable
def compose_functions(functions: List[Callable[[int], int]], x: int) -> int:
for func in reversed(functions):
x = func(x)
return x
functions = [
lambda x: x + 1,
lambda x: x * x,
lambda x: 2 * x
]
x = 4
print(compose_functions(functions, x))import java.util.List;
import java.util.function.Function;
public class FunctionComposition {
public static int composeFunctions(List<Function<Integer, Integer>> functions, int x) {
for (int i = functions.size() - 1; i >= 0; i--) {
x = functions.get(i).apply(x);
}
return x;
}
public static void main(String[] args) {
List<Function<Integer, Integer>> functions = List.of(
x -> x + 1,
x -> x * x,
x -> 2 * x
);
int x = 4;
System.out.println(composeFunctions(functions, x));
}
}#include <iostream>
#include <vector>
#include <functional>
int composeFunctions(std::vector<std::function<int(int)>> &functions, int x) {
for (auto it = functions.rbegin(); it != functions.rend(); ++it) {
x = (*it)(x);
}
return x;
}
int main() {
std::vector<std::function<int(int)>> functions = {
[](int x) { return x + 1; },
[](int x) { return x * x; },
[](int x) { return 2 * x; }
};
int x = 4;
std::cout << composeFunctions(functions, x) << std::endl;
return 0;
}function composeFunctions(functions, x) {
for (let i = functions.length - 1; i >= 0; i--) {
x = functions[i](x);
}
return x;
}
const functions = [
x => x + 1,
x => x * x,
x => 2 * x
];
const x = 4;
console.log(composeFunctions(functions, x));#include <stdio.h>
int composeFunctions(int (*functions[])(int), int length, int x) {
for (int i = length - 1; i >= 0; --i) {
x = functions[i](x);
}
return x;
}
int addOne(int x) { return x + 1; }
int square(int x) { return x * x; }
int doubleValue(int x) { return 2 * x; }
int main() {
int (*functions[])(int) = { addOne, square, doubleValue };
int x = 4;
int result = composeFunctions(functions, 3, x);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int ComposeFunctions(List<Func<int, int>> functions, int x) {
for (int i = functions.Count - 1; i >= 0; i--) {
x = functions[i](x);
}
return x;
}
static void Main() {
var functions = new List<Func<int, int>> {
x => x + 1,
x => x * x,
x => 2 * x
};
int x = 4;
Console.WriteLine(ComposeFunctions(functions, x));
}
}This Python solution uses a list of lambda functions. The functions are applied in reverse order to an initial value x using a loop.
Time Complexity: O(n) where n is the number of functions.
Space Complexity: O(1).
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.
from typing import List, Callable
def recursive_compose(functions: List[Callable[[int], int]], index: int, x: int) -> int:
if index < 0:
return x
return recursive_compose(functions, index - 1, functions[index](x))
functions = [
lambda x: x + 1,
lambda x: x * x,
lambda x: 2 * x
]
x = 4
print(recursive_compose(functions, len(functions) - 1, x))import java.util.List;
import java.util.function.Function;
public class FunctionComposition {
public static int recursiveCompose(List<Function<Integer, Integer>> functions, int index, int x) {
if (index < 0) return x;
x = functions.get(index).apply(x);
return recursiveCompose(functions, index - 1, x);
}
public static void main(String[] args) {
List<Function<Integer, Integer>> functions = List.of(
x -> x + 1,
x -> x * x,
x -> 2 * x
);
int x = 4;
System.out.println(recursiveCompose(functions, functions.size() - 1, x));
}
}#include <iostream>
#include <vector>
#include <functional>
int recursiveCompose(std::vector<std::function<int(int)>> &functions, int index, int x) {
if (index < 0) return x;
x = functions[index](x);
return recursiveCompose(functions, index - 1, x);
}
int main() {
std::vector<std::function<int(int)>> functions = {
[](int x) { return x + 1; },
[](int x) { return x * x; },
[](int x) { return 2 * x; }
};
int x = 4;
std::cout << recursiveCompose(functions, functions.size() - 1, x) << std::endl;
return 0;
}function recursiveCompose(functions, index, x) {
if (index < 0) return x;
return recursiveCompose(functions, index - 1, functions[index](x));
}
const functions = [
x => x + 1,
x => x * x,
x => 2 * x
];
const x = 4;
console.log(recursiveCompose(functions, functions.length - 1, x));#include <stdio.h>
int identity(int x) { return x; }
int recursiveCompose(int (*functions[])(int), int length, int x) {
if (length == 0) return identity(x);
int lastFunctionResult = functions[length - 1](x);
return recursiveCompose(functions, length - 1, lastFunctionResult);
}
int addOne(int x) { return x + 1; }
int square(int x) { return x * x; }
int doubleValue(int x) { return 2 * x; }
int main() {
int (*functions[])(int) = { addOne, square, doubleValue };
int x = 4;
int result = recursiveCompose(functions, 3, x);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int RecursiveCompose(List<Func<int, int>> functions, int index, int x) {
if (index < 0) return x;
x = functions[index](x);
return RecursiveCompose(functions, index - 1, x);
}
static void Main() {
var functions = new List<Func<int, int>> {
x => x + 1,
x => x * x,
x => 2 * x
};
int x = 4;
Console.WriteLine(RecursiveCompose(functions, functions.Count - 1, x));
}
}Python's recursive solution entails decrementing indices to apply each function till the list is exhausted, yielding a composed effect.
Time Complexity: O(n) where n is the function count.
Space Complexity: O(n) from recursion stack depth.
Approach 3: Default Approach
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
*/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 function count. |
| Default Approach | – |
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 |
Frequently asked questions
Is Function Composition easy or hard?
Function Composition is classified as an Easy problem. The main requirement is understanding how function outputs flow into subsequent function calls, combined with simple array traversal.
Function Composition Python/Java solution
In Python or Java, store the functions in a list or array and apply them from the last index to the first when the returned function executes. JavaScript solutions typically return a closure that performs this loop when called.
How to solve Function Composition in O(n)?
Start with the input value x and iterate through the function array from right to left. For each index i, update the value with functions[i](currentValue). After processing all functions, return the final value. This executes n function calls, giving O(n) time complexity.
What is the best approach for Function Composition?
The iterative right-to-left composition approach is the most practical solution. Iterate from the last function to the first and repeatedly apply each function to the running value. This processes all functions in O(n) time with O(1) extra space.
Is Function Composition asked at Google/Amazon/Meta?
Function composition problems appear in interviews that test JavaScript fundamentals or functional programming concepts. Variants of this question show up in front-end or full-stack interviews where candidates must demonstrate understanding of higher-order functions.
What data structure is used in Function Composition?
The problem primarily uses an array to store the list of functions. The algorithm simply traverses the array and applies each function sequentially, passing the result along the chain.
What is the time complexity of Function Composition?
Each invocation of the composed function calls every function in the array exactly once. If there are n functions, the total runtime is O(n). The iterative solution uses O(1) extra space, while the recursive approach requires O(n) stack space.