Problem Description

This problem asks you to implement a partial function application mechanism in JavaScript/TypeScript.

You need to create a function partial that takes two parameters:

• fn: A function to be partially applied
• args: An array of arguments that may contain placeholders

The partial function should return a new function partialFn that:

1. Replaces placeholders: When partialFn is called with restArgs, it should replace any "_" placeholders in the original args array with values from restArgs in order. For example, if args = [1, "_", 3, "_"] and restArgs = [2, 4], the placeholders get replaced to form [1, 2, 3, 4].

2. Appends remaining arguments: If there are more values in restArgs than there are placeholders, the extra values should be appended to the end of the arguments list. For example, if args = [1, "_"] and restArgs = [2, 3, 4], the final arguments become [1, 2, 3, 4].

3. Calls the original function: Finally, partialFn should call the original function fn with the modified arguments array spread as individual parameters and return its result.

Example:

function add(a, b, c) {
    return a + b + c;
}

const partialAdd = partial(add, [1, "_", 3]);
partialAdd(2); // Returns 6 (calls add(1, 2, 3))

const partialAdd2 = partial(add, ["_", "_"]);
partialAdd2(1, 2, 3, 4); // Returns 6 (calls add(1, 2, 3, 4), extra argument 4 is passed but ignored by add)

The key challenge is to correctly track and replace placeholders while maintaining the order of arguments and handling any excess arguments appropriately.

Intuition

The key insight is that we need to create a closure that "remembers" the original function and arguments template, then fills in the blanks when the returned function is called.

Think of it like a form with some fields already filled in and some blank spaces marked with "_". When someone provides the missing information (restArgs), we need to:

1. Fill in the blanks in order
2. Add any extra information at the end

The natural approach is to iterate through the original args array and whenever we encounter a placeholder "_", we replace it with the next available value from restArgs. We need a pointer (i) to track which value from restArgs we should use next.

Here's the step-by-step thought process:

1. Two-pointer technique: We need one pointer (j) to traverse the args array and another pointer (i) to track our position in restArgs. This ensures we fill placeholders in the correct order.

2. In-place replacement: When we find a "_" in args[j], we replace it with restArgs[i] and increment i to move to the next replacement value.

3. Handle excess arguments: After replacing all placeholders, if we still have unused values in restArgs (when i < restArgs.length), these should be appended to the end. This allows for functions that can accept variable numbers of arguments.

4. Spread operator for function call: Finally, we use the spread operator fn(...args) to pass the modified array as individual arguments to the original function, which is exactly how the original function expects to receive them.

The beauty of this solution is its simplicity - it modifies the args array directly during execution, making the logic straightforward and efficient with O(n) time complexity where n is the length of the arguments.

Solution Approach

The implementation uses a closure pattern to create a function that captures both the original function fn and the argument template args.

Here's the step-by-step implementation:

1. Return a closure function: The partial function returns an anonymous function that accepts ...restArgs (using rest parameters to collect all arguments into an array).

2. Initialize pointer for restArgs: We start with i = 0 to track our current position in the restArgs array.

3. Replace placeholders in args:

   for (let j = 0; j < args.length; ++j) {
       if (args[j] === '_') {
           args[j] = restArgs[i++];
       }
   }

   • Iterate through each element in args using index j
   • When we find a placeholder "_", replace it with restArgs[i]
   • Increment i after each replacement to move to the next value in restArgs
   • Non-placeholder values in args remain unchanged

4. Append remaining arguments:

   while (i < restArgs.length) {
       args.push(restArgs[i++]);
   }

   • After replacing all placeholders, check if there are unused values in restArgs
   • Append any remaining values to the end of args
   • This handles cases where restArgs has more values than there are placeholders

5. Call the original function:

   return fn(...args);

   • Use the spread operator to pass the modified args array as individual arguments
   • Return the result of calling fn with these arguments

Important Note: This implementation modifies the args array in place. In a production environment, you might want to create a copy of args first to avoid side effects if the same partial function is called multiple times:

const newArgs = [...args];  // Create a copy
// Then work with newArgs instead of args

The time complexity is O(n + m) where n is the length of args and m is the length of restArgs. The space complexity is O(1) if we modify in place, or O(n) if we create a copy of the args array.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works:

function multiply(a, b, c) {
    return a * b * c;
}

const partialMultiply = partial(multiply, [2, "_", "_"]);
const result = partialMultiply(3, 4, 5);  // What happens here?

Step 1: Create the partial function

• We call partial(multiply, [2, "_", "_"])
• This returns a new function that "remembers" fn = multiply and args = [2, "_", "_"]

Step 2: Call the partial function with restArgs = [3, 4, 5]

Now let's trace through the algorithm:

Initialize pointer: i = 0 (points to first element of restArgs)

Replace placeholders loop:

• j = 0: args[0] = 2 (not "_"), skip
• j = 1: args[1] = "_" → Replace with restArgs[0] = 3, increment i to 1
  • args becomes [2, 3, "_"]
• j = 2: args[2] = "_" → Replace with restArgs[1] = 4, increment i to 2
  • args becomes [2, 3, 4]

Append remaining arguments:

• i = 2, restArgs.length = 3, so i < restArgs.length is true
• Append restArgs[2] = 5 to args
• args becomes [2, 3, 4, 5]

Call original function:

• Execute multiply(...[2, 3, 4, 5]) which is multiply(2, 3, 4, 5)
• Since multiply only uses 3 parameters, it computes 2 * 3 * 4 = 24
• The extra argument 5 is ignored

Result: Returns 24

This example demonstrates all key aspects:

1. Preserving non-placeholder values (the 2)
2. Replacing placeholders in order ("_" → 3, then "_" → 4)
3. Appending excess arguments (the 5)
4. Proper function invocation with spread operator

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the total number of arguments (args.length + restArgs.length)

• The first for loop iterates through args.length elements: O(args.length)
• The while loop iterates through remaining restArgs elements: O(restArgs.length)
• The spread operation fn(...args) takes O(args.length) time to pass arguments
• Overall: O(args.length + restArgs.length) = O(n)

Space Complexity: O(n) where n is the total number of arguments

• The returned function creates a closure that captures the original args array: O(args.length)
• The args array is mutated in place, but can grow by pushing remaining restArgs: worst case O(args.length + restArgs.length)
• The spread operation creates a temporary argument list: O(args.length)
• Overall: O(args.length + restArgs.length) = O(n)

Note: There's a bug in this implementation - the args array is mutated on each call to the returned function, which means the function will not work correctly if called multiple times. The placeholders '_' will be permanently replaced after the first call.

Common Pitfalls

1. Mutating the Original Args Array

The most critical pitfall is modifying the original args array in place. This causes the partial function to behave incorrectly when called multiple times.

Problem Example:

def add(a, b, c):
    return a + b + c

# BAD: Modifying args directly
def partial_buggy(fn, args):
    def wrapper(*rest_args):
        rest_index = 0
        # Directly modifying args - BUG!
        for i in range(len(args)):
            if args[i] == '_':
                args[i] = rest_args[rest_index]
                rest_index += 1
        # ... rest of code
        return fn(*args)
    return wrapper

partial_add = partial_buggy(add, ['_', '_', 3])
print(partial_add(1, 2))  # Returns 6 (correct)
print(partial_add(4, 5))  # Returns 12 (incorrect! Should also be 12, but args is now [1, 2, 3])

Solution: Always create a copy of the args array:

def wrapper(*rest_args):
    final_args = args.copy()  # Create a copy!
    # Now work with final_args instead of args

2. Not Handling Insufficient Rest Arguments

When there are more placeholders than provided rest arguments, the code might crash or leave placeholders unreplaced.

Problem Example:

partial_add = partial(add, ['_', '_', '_'])
partial_add(1, 2)  # Only 2 arguments for 3 placeholders

Solution: Check bounds before accessing rest_args:

for i in range(len(final_args)):
    if final_args[i] == '_':
        if rest_args_index < len(rest_args):  # Bounds check
            final_args[i] = rest_args[rest_args_index]
            rest_args_index += 1
        # Optionally: else leave as '_' or replace with None/default value

3. Using Wrong Comparison for Placeholder Check

Using is instead of == for string comparison can fail unexpectedly due to Python's string interning behavior.

Problem Example:

# BAD: Using identity comparison
if args[i] is '_':  # May not work reliably
    # ...

# GOOD: Using equality comparison
if args[i] == '_':  # Always works correctly
    # ...

4. Not Preserving Function Metadata

The wrapper function loses the original function's metadata (name, docstring, etc.).

Solution: Use functools.wraps decorator:

from functools import wraps

def partial(fn, args):
    @wraps(fn)  # Preserves fn's metadata
    def wrapper(*rest_args):
        # ... implementation
    return wrapper