2666. Allow One Function Call

Easy

Problem Description

The problem statement requires us to create a higher-order function that takes a function fn as an argument and returns a new function. This new function must retain the behavior of the original fn, with the exception that it can only successfully execute once. This means that the very first time the new function is called, it should invoke fn, pass all given arguments to it, and then return the result of fn. Any calls to the new function after the first call should return undefined without invoking fn again. This ensures that fn is called at most once, regardless of how many times the new function is called.

Intuition

To build a solution for this problem, we need to create a function that "remembers" if it has been called before. We can achieve this by using a closure - a programming pattern that allows a function to access variables from the scope in which it was created, even after that scope has closed. We define a boolean variable called within the scope of the once function but outside of the scope of the returned function. This variable called is set to false initially, indicating that fn has not been called yet.

When the returned function is invoked for the first time, it checks called which is false, so it proceeds to set called to true to mark that fn has been called and then invokes fn with all the arguments it received using the ...args spread syntax for parameters. It then returns whatever fn returns. For subsequent invocations, when the returned function is called again, called is now true, and the function simply returns undefined without calling fn. This logic ensures that fn is executed only once and enforces the restriction as specified by the problem description.

The TypeScript type annotations in the solution enforce that the types of the arguments and return of the returned function match those of the original function fn. This is done using generic type parameters and utility types like Parameters and ReturnType to derive the appropriate types for the arguments and return value of fn.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Solution Approach

The problem requires a solution that ensures a given function fn is only called once, regardless of how many times the newly created function is called. The solution provided uses a closure to capture the state of whether fn has already been called.

Here's the step-by-step implementation of the solution:

Create Closure: The main function once is given fn as an argument. Inside once, a variable called is declared and initialized to false. This variable captures the state within the closure of the function returned by once.
Return New Function: once returns a new function that takes a variable number of arguments using the ...args rest syntax. This is where the closure comes into play. The variables defined in the scope of once (fn and called) are accessible to this returned function.
Check and Invoke: Every time the returned function is called, it first checks the value of called. If called is false, it means fn has not been called before, and the current invocation is the first.
- The called variable is set to true to prevent any further invocation of fn.
- fn is called with all arguments passed to the returned function, using fn(...args), and the result is returned to the caller.
Subsequent Calls: If called is already true when the function is invoked (meaning fn has been called before), the function skips the invocation of fn and returns undefined.

The advantage of using a closure in this situation is that it allows us to maintain the state (called) across multiple invocations of the returned function without affecting the global scope or the scope of the function passed to once. Furthermore, the state is encapsulated within the returned function, adhering to good coding practices.

The solution approach also uses TypeScript generics and utility types for type inference:

T extends (...args: any[]) => any defines a generic type T for the function which can take any number of arguments and return any type.
Parameters<T> is a utility type that extracts the argument types of T so we can ensure the returned function accepts the same types of arguments.
ReturnType<T> is used to specify that the returned function should have the same return type as fn.

In conclusion, the implementation uses a combination of closures, generically typed functions, and control flow based on a boolean flag to satisfy the provided problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Heap sortMerge sortInsertion sortQuick sort

I don’t know

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have a function fn that simply multiplies any two numbers and returns the result. We want to ensure that fn can only be invoked once.

Firstly, we define the function fn:

1function fn(x, y) {
2  return x * y;
3}

Now, following the solution approach, we implement the once function:

1function once<T extends (...args: any[]) => any>(fn: T): (...args: Parameters<T>) => ReturnType<T> | undefined {
2  let called = false;
3
4  return function(...args: Parameters<T>): ReturnType<T> | undefined {
5    if (!called) {
6      called = true;
7      return fn(...args);
8    }
9    return undefined;
10  };
11}

Next, we wrap fn using once to create the onceFn function which will be our higher-order function:

1const onceFn = once(fn);

Now, let's walk through how this would work:

We call onceFn with arguments 2 and 3 for the first time.

1const result = onceFn(2, 3); // 'onceFn' invokes 'fn', calculates 2 * 3, and returns 6
2console.log(result); // Outputs: 6

During this initial call:

The called variable is still false at the start.
The onceFn sees that fn hasn't been called, so it sets called to true.
It invokes fn with the given arguments and returns the result.

We attempt to call onceFn again with any arguments - let's say 4 and 5:

1const secondResult = onceFn(4, 5); // 'onceFn' does not invoke 'fn' this time, returns `undefined`
2console.log(secondResult); // Outputs: undefined

On this second invocation:

The called variable is already true.
The onceFn does not call fn again and simply returns undefined.

The internal called state is maintained across these calls due to the closure created within the once function. The onceFn has remembered that fn has already been invoked once, and it upholds our rule that fn only gets called one time. This example illustrates the utility of closures to encapsulate state in a functional programming context, while also showing how TypeScript can be used to maintain type safety in higher-order function scenarios.

Solution Implementation

1# Define a generic function `once` which takes a function (`func`) and returns
2# a new function that can be called only once. Subsequent calls return the result
3# of the first invocation, otherwise returns None.
4
5def once(func):
6    """
7    Creates a function that invokes `func` once, no matter how many times it is called.
8    Subsequent calls to the created function return the result of the first invocation.
9  
10    :param func: The function to restrict to be called once.
11    :return: A new function that is restricted to invoking `func` only once.
12    """
13    # A list is used here to hold `called` and `result` as it can be modified within the inner function.
14    # In Python, nonlocal variables cannot be primitive types when modified within an inner function.
15    called_and_result = [False, None]
16
17    def wrapper(*args, **kwargs):
18        if not called_and_result[0]:
19            called_and_result[0] = True  # Update the state to prevent further invocations.
20            # Call the original function with the provided arguments and store the result.
21            called_and_result[1] = func(*args, **kwargs)
22        return called_and_result[1]  # Return the stored result or None if function has been called before.
23
24    return wrapper
25
26# Example usage:
27
28# Define `sum_fn` as a function that takes three numbers and returns their sum.
29def sum_fn(a, b, c):
30    """Function that calculates the sum of three numbers."""
31    return a + b + c
32
33# Create a function `once_sum_fn` that encapsulates `sum_fn` and restricts it to a single call.
34once_sum_fn = once(sum_fn)
35
36# Call `once_sum_fn` with arguments (1, 2, 3). It should return 6.
37print(once_sum_fn(1, 2, 3))  # Expected output: 6
38
39# Attempt to call `once_sum_fn` with different arguments (2, 3, 6).
40# Since `once_sum_fn` was already called, it should return None without calling `sum_fn`.
41print(once_sum_fn(2, 3, 6))  # Expected output: None
42

1import java.util.function.Function;
2
3// Create a generic functional interface `OnceFunction` that extends Function,
4// specifying its argument and return type with generics.
5@FunctionalInterface
6interface OnceFunction<T, R> extends Function<T, R> {
7    // Override the apply method from Function to define custom behavior.
8    @Override
9    R apply(T t);
10}
11
12public class OnceExample {
13
14    /**
15     * Creates a function that invokes the given function once, no matter how many times it's called.
16     * Subsequent calls to the created function return the result of the first invocation.
17     *
18     * @param func The function to restrict to a single call.
19     * @param <T>  The input type of the function.
20     * @param <R>  The return type of the function.
21     * @return A new function that is restricted to invoking the given function only once.
22     */
23    public static <T, R> OnceFunction<T, R> once(Function<T, R> func) {
24        // Create a new instance of `OnceFunction`.
25        return new OnceFunction<>() {
26            // A flag to keep track if the function has been called.
27            private boolean called = false;
28
29            // The result of the first call to remember.
30            private R firstResult = null;
31
32            @Override
33            public R apply(T t) {
34                // Check if the function has not been called yet.
35                if (!called) {
36                    // If not, invoke the function with the provided arguments and store the result.
37                    firstResult = func.apply(t);
38                    // Update the state to prevent further invocations.
39                    called = true;
40                    // Return the stored result.
41                    return firstResult;
42                }
43                // If the function was already called, return the stored result.
44                return firstResult;
45            }
46        };
47    }
48
49    // Example usage:
50    public static void main(String[] args) {
51        // Define a function that takes an integer array and returns the sum of all elements.
52        Function<int[], Integer> sumFn = (int[] numbers) -> {
53            int sum = 0;
54            for (int n : numbers) {
55                sum += n;
56            }
57            return sum;
58        };
59
60        // Create a once-wrappable version of the `sumFn` function.
61        OnceFunction<int[], Integer> onceSumFn = OnceExample.once(sumFn);
62
63        // Call `onceSumFn` with an integer array. It should return the sum of the numbers.
64        System.out.println(onceSumFn.apply(new int[]{1, 2, 3})); // Expected output: 6
65
66        // Attempt to call `onceSumFn` again, this time with a different integer array.
67        // Since `onceSumFn` has already been called, it should return the result of the first call.
68        System.out.println(onceSumFn.apply(new int[]{2, 3, 4})); // Expected output: 6
69    }
70}
71

1#include <iostream>
2#include <functional>
3#include <tuple>
4
5// Define a template for a function that takes any number and type of arguments and
6// returns a `std::optional` value of the function's return type.
7template<typename Func>
8class OnceFunction {
9public:
10    using ReturnType = std::optional<std::invoke_result_t<Func, decltype(std::placeholders::_1)>>;
11
12    OnceFunction(Func&& fn) : function_(std::forward<Func>(fn)), called_(false) {}
13
14    // A function to invoke the stored function only once. Subsequent calls return `std::nullopt`.
15    template<class... Args>
16    ReturnType operator()(Args... args) {
17        if (!called_) {
18            called_ = true; // Mark as called
19            return function_(std::forward<Args>(args)...);
20        }
21        return std::nullopt; // Function was already called, return `std::nullopt`
22    }
23
24private:
25    Func function_; // The original function that should be called at most once.
26    bool called_; // Boolean flag to track if the function has been called or not.
27};
28
29/**
30 * Creates a function that invokes `func` once, no matter how many times it is called. Subsequent calls
31 * to the created function return `std::nullopt`.
32 * @param func - The function to restrict to be called once.
33 * @returns An `OnceFunction` functor that invokes `func` only once.
34 */
35template<typename Func>
36auto once(Func&& func) {
37    return OnceFunction<Func>(std::forward<Func>(func));
38}
39
40// Example usage of the once function template:
41
42// A function that takes three numbers and returns their sum.
43auto sumFn = [](int a, int b, int c) -> int {
44    return a + b + c;
45};
46
47int main() {
48    // Create a function `onceSumFn` that encapsulates `sumFn` and restricts it to a single call.
49    auto onceSumFn = once(sumFn);
50
51    // Call `onceSumFn` with arguments (1, 2, 3). It should return the sum, 6.
52    std::cout << "First call result: ";
53    if (auto result = onceSumFn(1, 2, 3); result) {
54        std::cout << *result << std::endl; // Expected output: First call result: 6
55    } else {
56        std::cout << "undefined" << std::endl;
57    }
58
59    // Attempt to call `onceSumFn` again with different arguments (2, 3, 6).
60    // Since `onceSumFn` was already called, it should return 'undefined' without calling `sumFn`.
61    std::cout << "Second call result: ";
62    if (auto result = onceSumFn(2, 3, 6); result) {
63        std::cout << *result << std::endl;
64    } else {
65        std::cout << "undefined" << std::endl; // Expected output: Second call result: undefined
66    }
67
68    return 0;
69}
70

1// Define a generic function type `OnceFunction` which takes a function with any number and types of arguments
2// and returns its return type or undefined.
3type OnceFunction<T extends (...args: any[]) => any> = (...args: Parameters<T>) => ReturnType<T> | undefined;
4
5/**
6 * Creates a function that invokes `func` once, no matter how many times it is called. Subsequent calls
7 * to the created function return the result of the first invocation.
8 * @param func - The function to restrict to be called once.
9 * @returns A new function that is restricted to invoking `func` only once.
10 */
11function once<T extends (...args: any[]) => any>(func: T): OnceFunction<T> {
12    // Declare a variable to track if the function has been called.
13    let called = false;
14  
15    // Return a new function that captures arguments and invokes the original function only if not called before.
16    return function (...args: Parameters<T>): ReturnType<T> | undefined {
17        // Check if the function has already been called.
18        if (!called) {
19            // Update the state to prevent further invocations.
20            called = true;
21            // Call the original function with the provided arguments and return its result.
22            return func(...args);
23        }
24        // If the function was called before, return undefined.
25        // No further action is taken, and the original function is not called.
26    };
27}
28
29// Example usage:
30// Let `sumFn` be a function that takes three numbers and returns their sum.
31let sumFn = (a: number, b: number, c: number) => a + b + c;
32
33// Create a function `onceSumFn` that encapsulates `sumFn` and restricts it to a single call.
34let onceSumFn = once(sumFn);
35
36// Call `onceSumFn` with arguments (1, 2, 3). It should return 6.
37console.log(onceSumFn(1, 2, 3)); // Expected output: 6
38
39// Attempt to call `onceSumFn` with different arguments (2, 3, 6).
40// Since `onceSumFn` was already called, it should return undefined without calling `sumFn`.
41console.log(onceSumFn(2, 3, 6)); // Expected output: undefined
42

Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

O(1)O(n)O(n!)O(n^n)

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the once function wrapper is O(1), also referred to as constant time complexity. This is because the wrapper does not perform any operations that scale with the size of the input, it only checks a boolean flag and, if not previously called, executes the function fn once. The time complexity of calling the wrapped fn function is not included in the complexity of the once wrapper itself. When the original function fn is called via onceFn, its time complexity is dependent on the implementation of fn.

Space Complexity

The space complexity of the once function wrapper is O(1), which means it uses a constant amount of space. It only allocates space for one boolean variable called. It does not allocate additional space that grows with the size of the input. However, the space complexity of the closure that includes the fn function and the called value is subject to the space requirements of fn itself, which are not accounted for in the once wrapper's space complexity.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2666. Allow One Function Call

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings