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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    
    
    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

1
2
3
4
5
6
7


    
    
    Input: functions = [], x = 42
    Output: 42
    Explanation:
    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

Method 1 – Reduce Right Function Composition

Intuition

To compose a list of functions so that f(g(h(x))) is applied, we need to apply the functions from right to left. If the list is empty, the identity function should be returned.

Approach

  1. If the list of functions is empty, return a function that returns its input (identity function).
  2. Otherwise, use reduceRight to compose the functions from right to left.
  3. The composed function applies each function to the result of the previous one.

Code

1
2
3
4
5
6

class Solution {
  compose(functions) {
    if (functions.length === 0) return x => x;
    return functions.reduceRight((acc, fn) => x => fn(acc(x)));
  }
}
1
2
3
4
5
6

class Solution {
  compose(functions: ((x: number) => number)[]): (x: number) => number {
    if (functions.length === 0) return (x: number) => x;
    return functions.reduceRight((acc, fn) => (x: number) => fn(acc(x)));
  }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of functions, since each function is composed once.
  • 🧺 Space complexity: O(1), as only a few variables are used for composition.