How do you solve Function Composition on LeetCode?

Function Composition (LeetCode #2629) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Function composition is evaluated from right to left.

What is the brute force solution for Function Composition?

The brute force approach for Function Composition is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves executing each function in the array sequentially, starting from the last function and passing the result to the previous one. This is straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Function Composition?

Clarify the problem requirements and constraints before coding. Think aloud to show your thought process to the interviewer. Test your solution with edge cases, such as an empty array or a single function.

What are common mistakes when solving Function Composition?

Not handling the case of an empty functions array. Confusing the order of function application.

#2629

Function Composition

Easy

Function CompositionHigher-Order Functions

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages the same logic as the brute force approach but is more efficient in terms of clarity and execution. We directly create a new function that applies all functions in a single pass without unnecessary complexity.

⚙️

Algorithm

5 steps

1Step 1: Define a function that takes an integer 'x'.
2Step 2: Initialize 'result' with 'x'.
3Step 3: Loop through the functions in reverse order.
4Step 4: Update 'result' with the output of each function applied to the current 'result'.
5Step 5: Return the final 'result'.

solution.py9 lines

1# Full working Python code
2
3def compose(functions):
4    def fn(x):
5        result = x
6        for f in reversed(functions):
7            result = f(result)
8        return result
9    return fn

ℹ

Complexity note: The time complexity is O(n) because we loop through the functions once. The space complexity is O(1) as we are only using a fixed amount of space for variables.

1Function composition is evaluated from right to left.
2An empty list of functions returns the identity function.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.