💬 Discord
Sign In
NeetCode #950LC-2629EasyJavaScript
← Back to All Problems

#950 · #2629 · Function Composition(函数组合)

📌 Problem Statement & Constraints

Given an array of functions functions, return a new function fn(x) whose result is the right-to-left composition of all of them. For example, [f, g, h] composes to f(g(h(x))).

💡 Core Algorithmic Approaches

  1. Composition is right to left: the last function in the array is applied to x first.
  2. Implement by looping from functions.length - 1 down to 0, updating x = functions[i](x).
  3. When the array is empty the loop never runs and x is returned unchanged — the identity function, as required.
  4. functions.reduceRight((acc, f) => f(acc), x) is the equivalent built-in form.

💻 Benchmark Python3 Implementation

var compose = function(functions) {
    return function(x) {
        // Apply right to left; an empty array returns x (the identity function)
        for (let i = functions.length - 1; i >= 0; i--) {
            x = functions[i](x);
        }
        return x;
    };
};

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(k): one call per function.
💾 Space Complexity
O(1): only the running value is stored.

⚠️ Interview Pitfalls & Follow-ups

  • Applying left to right: composition is right to left, since the mathematical f(g(x)) applies g first.
  • Using reduce instead of reduceRight: plain reduce reverses the intended order.
  • Throwing on an empty array: the correct behaviour is to return x unchanged.