LeetCode 2797 - Partial Function with Placeholders

The problem is asking us to implement a function partial that takes a target function fn and a list of arguments args. Some of these arguments may be placeholders represented by the string "".

leetcodeeasy

LeetCode Problem 2797

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

The problem is asking us to implement a function partial that takes a target function fn and a list of arguments args. Some of these arguments may be placeholders represented by the string "_". When the returned function partialFn is called with additional arguments restArgs, each placeholder in args should be replaced with elements from restArgs in order. If there are leftover elements in restArgs after all placeholders are replaced, they should be appended to the end of args. Finally, fn should be invoked with the modified args passed as separate arguments, and the result returned.

In simpler terms, the problem is about creating a partially applied function that supports placeholders and additional arguments dynamically. The inputs are:

  • fn: a callable function that can take a variable number of arguments.
  • args: an initial list of arguments where "_" denotes a placeholder.
  • restArgs: a list of arguments to fill the placeholders and any leftover positions.

The output is the return value of fn after merging args and restArgs according to the rules.

Constraints show that args and restArgs can be large (up to 50,000 elements each), so we need an approach that avoids excessive copying or nested loops over the arrays. The number of placeholders will never exceed restArgs.length, ensuring we always have enough values to replace them.

Important edge cases include having no placeholders, having all elements as placeholders, or having extra elements in restArgs that need to be appended.

Approaches

The brute-force approach would involve iterating over args for each call to partialFn and replacing each "_" with the next available value from restArgs. After replacing all placeholders, we would concatenate any remaining restArgs. This approach works correctly but may be inefficient if repeatedly copying arrays or lists for very large inputs.

The key insight for the optimal solution is that we can build the merged argument list in a single pass through args while tracking the index in restArgs. This avoids multiple concatenations or iterations. After the placeholders are replaced, we append any remaining restArgs in constant time. The resulting list can then be passed to fn using argument unpacking (*args in Python or ... in Go).

Approach Time Complexity Space Complexity Notes
Brute Force O(n + m) O(n + m) Iterates over args and restArgs separately; works but may do unnecessary copying
Optimal O(n + m) O(n + m) Single pass merge with placeholder replacement; direct construction of final arguments list

Algorithm Walkthrough

  1. Initialize an empty list final_args to hold the merged arguments.
  2. Initialize an index rest_index = 0 to track our position in restArgs.
  3. Iterate over each element arg in args:
  • If arg is "_", replace it with restArgs[rest_index] and increment rest_index.
  • Otherwise, keep arg as-is.
  • Append the resulting value to final_args.
  1. After processing all elements in args, append any remaining elements from restArgs[rest_index:] to final_args.
  2. Invoke fn with final_args unpacked as arguments and return the result.

Why it works: The algorithm guarantees that all placeholders are replaced in order, and any leftover arguments are appended at the end. By iterating linearly through args and keeping track of restArgs, we ensure the correct mapping and ordering of arguments for fn.

Python Solution

from typing import Any, Callable, List

def partial(fn: Callable, args: List[Any]) -> Callable:
    def partialFn(*restArgs: Any) -> Any:
        final_args = []
        rest_index = 0
        
        for arg in args:
            if arg == "_":
                final_args.append(restArgs[rest_index])
                rest_index += 1
            else:
                final_args.append(arg)
        
        final_args.extend(restArgs[rest_index:])
        return fn(*final_args)
    
    return partialFn

The implementation defines a closure partialFn to capture the original args and fn. Inside partialFn, we build final_args by replacing placeholders with elements from restArgs. Any leftover elements in restArgs are appended at the end. Finally, we call fn with unpacked arguments.

Go Solution

package main

func Partial(fn func(...any) any, args []any) func(...any) any {
    return func(restArgs ...any) any {
        finalArgs := make([]any, 0, len(args)+len(restArgs))
        restIndex := 0

        for _, arg := range args {
            if arg == "_" {
                finalArgs = append(finalArgs, restArgs[restIndex])
                restIndex++
            } else {
                finalArgs = append(finalArgs, arg)
            }
        }

        finalArgs = append(finalArgs, restArgs[restIndex:]...)
        return fn(finalArgs...)
    }
}

In Go, we preallocate finalArgs with enough capacity for efficiency. Placeholders are replaced sequentially, and remaining restArgs are appended. The main difference from Python is explicit slice handling and variadic arguments syntax.

Worked Examples

Example 1:

args restArgs final_args
[2,4,6] [8,10] [2,4,6,8,10]

No placeholders exist. restArgs is appended to args. Calling fn(*final_args) returns [2,4,6,8,10].

Example 2:

args restArgs final_args
[1,2,"",4,"",6] [3,5] [1,2,3,4,5,6]

Placeholders are replaced sequentially by 3 and 5 from restArgs. No leftovers remain. fn(*final_args) returns [1,2,3,4,5,6].

Example 3:

args restArgs final_args
["_",5] [5,20] [5,5,20]

Placeholder replaced by 5, leftover 20 appended. fn(*final_args) evaluates b + a - c as 5 + 5 - 20 = -10.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Linear pass through args (n) and leftover elements in restArgs (m)
Space O(n + m) We build a new list of size at most n + m for the merged arguments

The algorithm is efficient because it only processes each element of args and restArgs once and does not use nested iterations.

Test Cases

# Basic examples
assert partial(lambda *args: args, [2,4,6])(*[8,10]) == [2,4,6,8,10]  # no placeholders
assert partial(lambda *args: args, [1,2,"_",4,"_",6])(*[3,5]) == [1,2,3,4,5,6]  # multiple placeholders
assert partial(lambda a,b,c: b + a - c, ["_",5])(*[5,20]) == -10  # arithmetic example

# Edge cases
assert partial(lambda *args: args, ["_","_"])(*[1,2,3]) == [1,2,3]  # more restArgs than placeholders
assert partial(lambda *args: args, [1,2,3])(*[]) == [1,2,3]  # no restArgs
assert partial(lambda *args: args, ["_"])(*[10]) == [10]  # single placeholder
Test Why
[2,4,6], [8,10] No placeholders, check appending
[1,2,"",4,"",6], [3,5] Multiple placeholders, sequential replacement
["_",5], [5,20] Placeholder replacement with leftover restArgs
["",""], [1,2,3] Extra restArgs beyond placeholders
[1,2,3], [] No restArgs, ensure original args preserved
["_"], [10] Single placeholder, simplest case

Edge Cases

One important edge case is when there are more elements in restArgs than placeholders. Our implementation handles this by appending leftover elements after all placeholders are replaced, ensuring no data is lost.

Another edge case is when args contains no placeholders at all. In this situation, restArgs should simply be appended to the end. This is handled by the same logic without special casing.

A third edge case is when args is entirely placeholders. In this case, the algorithm will consume exactly as many elements from restArgs as needed to fill the placeholders, and any extra elements will be appended, ensuring fn always receives the correct number of arguments.