LeetCode 2629 - Function Composition

This problem asks us to implement function composition. We are given an array of functions and must return a new function that combines all of them into a single callable function.

leetcodeeasy

LeetCode Problem 2629

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

This problem asks us to implement function composition. We are given an array of functions and must return a new function that combines all of them into a single callable function.

In mathematics and programming, function composition means taking the output of one function and feeding it into the next. The important detail here is that the functions are applied from right to left.

For example, if the input array is:

[f(x), g(x), h(x)]

then the composed function behaves like:

f(g(h(x)))

This means h(x) executes first, then g(...), and finally f(...).

The input consists of:

  • An array of functions, where every function takes a single integer and returns a single integer.
  • A value x, which will later be passed into the composed function.

The expected output is not the final computed integer directly, but rather a new function. When this returned function is called with an integer x, it should apply all functions in the correct order and return the final result.

One important special case is when the function array is empty. In this scenario, there are no transformations to apply, so the result should be the identity function, meaning:

f(x) = x

The constraints tell us that:

  • functions.length <= 1000, which means there can be up to 1000 functions.
  • Each function accepts and returns a single integer.
  • x lies between -1000 and 1000.

Since the number of functions is relatively small, we do not need any sophisticated optimization. A simple linear traversal through the array is sufficient.

There are several important edge cases to consider. The first is an empty function list, which should return the identity function. Another case is when there is only one function, meaning the composition is simply that function itself. We must also be careful about evaluation order, because applying functions left to right instead of right to left would produce incorrect results.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to repeatedly compose functions one by one.

We can imagine taking the first function and manually wrapping it around the next function, then wrapping the result around the next one again until all functions are merged into a deeply nested function.

For example:

[f, g, h]

could become:

x => f(g(h(x)))

This works correctly because function composition is naturally recursive. However, building nested closures repeatedly may introduce unnecessary overhead and make the implementation harder to follow. Each composition step creates an additional function wrapper.

Although this approach is still acceptable for the problem constraints, it is conceptually more complicated than necessary.

Optimal Approach

The key insight is that we do not actually need to build nested function objects repeatedly. Instead, we can return a function that simply iterates through the input functions in reverse order and updates a running result.

When the returned function receives an input x:

  1. Start with result = x.
  2. Traverse the function array from the last function to the first.
  3. Apply each function to result.
  4. Return the final value.

This works because function composition is fundamentally just repeated transformation of a value. Since the required order is right to left, iterating backward naturally produces the correct behavior.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Builds nested function wrappers during composition
Optimal O(n) O(1) Iterates backward through functions and applies transformations directly

Algorithm Walkthrough

  1. Define and return a new function that accepts an integer x.
  2. Inside the returned function, initialize a variable called result with the input value x.

This variable stores the current transformed value as functions are applied one by one. 3. Traverse the functions array in reverse order.

We iterate backward because composition happens from right to left. The last function executes first. 4. For each function in the reversed order, update the result:

result = currentFunction(result)

This applies the transformation and prepares the output for the next function. 5. After all functions have been processed, return result. 6. If the array is empty, the loop never runs, so result remains equal to x.

This naturally implements the identity function without needing special handling.

Why it works

The algorithm maintains an important invariant: after processing the i-th function from the right, result equals the correct composition of all functions processed so far.

Initially, result = x, which is correct before any function has been applied. At each step, the next function in right-to-left order transforms the current value, preserving correctness. By the time the loop finishes, every function has been applied in the exact required order, producing:

f1(f2(...fn(x)))

which matches the problem definition.

Python Solution

from typing import List, Callable

class Solution:
    def compose(self, functions: List[Callable[[int], int]]) -> Callable[[int], int]:
        def composed_function(x: int) -> int:
            result = x

            for function in reversed(functions):
                result = function(result)

            return result

        return composed_function

The implementation closely follows the algorithm.

The compose method receives the list of functions and returns a new function called composed_function. This returned function accepts an integer x, which becomes the starting value for the composition process.

Inside composed_function, we initialize result = x. We then iterate through the functions in reverse order using reversed(functions). This is important because the problem explicitly requires right-to-left evaluation.

For each function, we update result by passing the current value into that function. Once every function has been applied, the final result is returned.

An important detail is that no explicit check for an empty array is necessary. If functions is empty, the loop simply never executes, and the function returns the original input x, which correctly behaves as the identity function.

Go Solution

func compose(functions []func(int) int) func(int) int {
	return func(x int) int {
		result := x

		for i := len(functions) - 1; i >= 0; i-- {
			result = functions[i](result)
		}

		return result
	}
}

The Go implementation follows the same logic as the Python version. Since Go does not have a built in equivalent to Python's reversed(), we iterate manually from len(functions) - 1 down to 0.

The returned anonymous function captures the functions slice through a closure. When called with an integer x, it applies each function in reverse order and returns the final result.

There is no special handling needed for an empty slice. If functions has length 0, the loop condition fails immediately and the original value x is returned, correctly implementing the identity function.

Because all values are integers and the problem constraints are small, integer overflow is not a concern in practice for this LeetCode problem.

Worked Examples

Example 1

Input:

functions = [x => x + 1, x => x * x, x => 2 * x]
x = 4

We process functions from right to left.

Step Function Applied Current Result
Start Initial value 4
1 2 * x 8
2 x * x 64
3 x + 1 65

Final output:

65

Example 2

Input:

functions = [x => 10 * x, x => 10 * x, x => 10 * x]
x = 1

Again, we evaluate from right to left.

Step Function Applied Current Result
Start Initial value 1
1 10 * x 10
2 10 * x 100
3 10 * x 1000

Final output:

1000

Example 3

Input:

functions = []
x = 42

Since there are no functions, nothing is applied.

Step Function Applied Current Result
Start Initial value 42

Final output:

42

This correctly matches the identity function behavior.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through every function exactly once
Space O(1) Only a single result variable is used

The runtime is linear in the number of functions because each function is applied exactly one time. Since n <= 1000, this is easily efficient enough.

The auxiliary space complexity is constant because we only maintain one running variable, result. We do not allocate extra data structures proportional to input size.

Test Cases

solution = Solution()

# Example 1
fn = solution.compose([
    lambda x: x + 1,
    lambda x: x * x,
    lambda x: 2 * x
])
assert fn(4) == 65  # Standard right-to-left composition

# Example 2
fn = solution.compose([
    lambda x: 10 * x,
    lambda x: 10 * x,
    lambda x: 10 * x
])
assert fn(1) == 1000  # Repeated multiplication

# Example 3
fn = solution.compose([])
assert fn(42) == 42  # Empty list, identity function

# Single function
fn = solution.compose([
    lambda x: x - 5
])
assert fn(10) == 5  # Only one transformation

# Negative numbers
fn = solution.compose([
    lambda x: x + 3,
    lambda x: -x
])
assert fn(-2) == 5  # Handles negatives correctly

# Verify right-to-left order
fn = solution.compose([
    lambda x: x + 2,
    lambda x: x * 3
])
assert fn(5) == 17  # (5 * 3) + 2

# Identity style function
fn = solution.compose([
    lambda x: x
])
assert fn(99) == 99  # No modification

# Large function chain
fn = solution.compose([lambda x: x + 1] * 1000)
assert fn(0) == 1000  # Stress test with max size
Test Why
Example 1 Validates standard composition order
Example 2 Confirms repeated transformations work
Example 3 Verifies identity function behavior
Single function Ensures one function works correctly
Negative numbers Tests handling of negative values
Right-to-left order Confirms evaluation direction
Identity function Verifies unchanged output
Large chain Stress tests maximum constraint size

Edge Cases

Empty Function Array

The most important edge case is when functions = []. A naive implementation might accidentally return None, throw an error, or fail because there is nothing to iterate over.

Our implementation handles this naturally. Since the reverse iteration loop never executes, result remains equal to the original input x, which correctly implements the identity function.

Single Function

When there is only one function in the array, composition should behave exactly like that function itself.

For example:

[x => x + 5]

should simply return:

x + 5

Our implementation handles this automatically because the loop executes exactly once.

Incorrect Evaluation Order

A common bug is applying functions from left to right instead of right to left.

For example:

[x => x + 2, x => x * 3]
x = 5

The correct result is:

(5 * 3) + 2 = 17

If processed left to right, the result would incorrectly become:

(5 + 2) * 3 = 21

By explicitly iterating in reverse order, our implementation guarantees the correct composition behavior.