2626. Array Reduce Transformation

Easy
Leetcode Link

Problem Description

In this problem, we are provided with an array of integers called nums, a reducer function fn, and an initial value init. The task is to produce a single value using a reduction process that applies fn to each successive element of nums, starting with init as the first argument and the first array element as the second argument, and then using the result as the new first argument in the next application with the subsequent array element. This process continues until every element in the array has been processed. The output of the final call to fn is what we will return as the result. In case nums is an empty array, we should simply return init. We are instructed to solve the problem without resorting to the built-in Array.reduce method available in many programming languages.

Intuition

To approach this solution, we naturally think of iterating through the array, element by element, and at each step applying the reducer function fn to the current result acc and the current element x. Starting with init as our accumulator acc, we update acc with the result of fn(acc, x) after each array element is processed. The use of a loop for iteration is a fundamental tool in programming, allowing us to apply the same operation for each element in a sequence - this fits perfectly with the task of reducing an array. The strength of the reducer pattern is that it's a general concept; the specific behavior is defined by the provided function fn, which makes this approach both flexible and powerful.

The given TypeScript solution follows this intuition directly:

  1. Initialize the accumulator acc with the provided initial value init.
  2. Iterate through each element x in the nums array, one by one.
  3. For each element x, apply the reducer function fn to the accumulator acc and x and update acc with the result.
  4. After processing all elements, return acc as it now represents the accumulation of the sequential applications of fn.

By following these steps, we adhere to the instructions and compute the reduced value expected by the problem description.

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

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Solution Approach

The implementation follows a straightforward pattern that's commonly used in functional programming, known as reduction or folding. The idea is to maintain a running total or combined result as we process a sequence of values.

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

  1. Initialization: We start by initializing an accumulator variable acc with the value of init, which is the initial value provided to us. In functional reduction, the accumulator is the placeholder for the ongoing result.

  2. Looping Through Elements: We then enter a loop that will iterate over each element in the nums array. This is done using a for...of statement in TypeScript, a language construct particularly well-suited for iterating over array elements.

  3. Applying the Reducer Function: Inside the loop, for each element x, we call the reducer function fn with acc and x as arguments. The return value of fn(acc, x) is then assigned back to acc. In mathematical terms, if fn is denoted as f, this step could be written as acc = f(acc, x). This updates the accumulator with the "reduced" value that incorporates the contribution of the current array element x.

  4. Returning the Result: After the loop has processed all of the elements, the final value of acc holds the reduced result of the entire array. We then exit the loop, and the function returns this final value.

  5. Handling Edge Cases: As per the problem description, if the array is empty (nums.length === 0), we simply return the initial value init. In the provided implementation, this is implicitly handled, as the loop will not iterate at all for an empty array, and acc, which still equals init, will be returned.

The algorithm runs in O(n) time complexity, where n is the number of elements in the array since it processes each element exactly once. The space complexity is O(1), as we only use a fixed amount of extra space for the accumulator.

The TypeScript implementation provided uses no complex data structures or patterns beyond a for loop, making it very accessible and easily understandable.

The implementation provided is algorithmically efficient and straightforward, which stands as a testament to the elegance of the reduce pattern.

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

Which of the following uses divide and conquer strategy?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we are given the following:

  • An array nums of integers: [3, 5, 2, 4]
  • A reducer function fn, which takes two integers and returns their sum.
  • An initial value init of 10.

Our goal is to reduce the array using the function fn and init as the starting point. Now, let's walk through the solution step by step:

  1. Initialization: We initialize an accumulator acc with the value of init which is 10.

  2. Looping Through Elements: We start an iteration over each element in the nums array:

    • First iteration: Take the first element 3, apply the reducer function fn(acc, x) => fn(10, 3) which returns 13. Update acc to 13.
    • Second iteration: Take the next element 5, apply the reducer function fn(acc, x) => fn(13, 5) which returns 18. Update acc to 18.
    • Third iteration: Take the next element 2, apply the reducer function fn(acc, x) => fn(18, 2) which returns 20. Update acc to 20.
    • Fourth iteration: Take the last element 4, apply the reducer function fn(acc, x) => fn(20, 4) which returns 24. Update acc to 24.

  3. Returning the Result: Having processed all elements in the array, acc now holds the value 24, which is the final reduced result.

  4. Handling Edge Cases: If nums were an empty array, the for loop would not run and we would simply return init, which is 10 in this case.

In this example, the final output, after reducing the array starting with an initial value of 10, is 24. The step-by-step reduction process consolidates all the values into one, applying the reducer function sequentially to each array element and the running accumulation.

Solution Implementation

1from typing import List, Callable
2
3# Type alias for the reducer function which is a callback that will be passed
4# to the reduce function. It takes two numbers, `accumulator` and `current_value`,
5# and returns a number.
6ReducerFunction = Callable[[int, int], int]
7
8def reduce(numbers: List[int], reducer: ReducerFunction, initial_value: int) -> int:
9    """
10    Applies a reducer function on each element of the `numbers` array, resulting in a single output value.
11  
12    :param numbers: The list of numbers to be reduced.
13    :param reducer: The function to execute on each element in the list.
14    :param initial_value: The initial value to start the accumulation from.
15    :return: The reduced value after all elements have been processed.
16    """
17    # The variable that will accumulate the result of calling the reducer
18    # function repeatedly.
19    accumulator = initial_value
20
21    # Iterate through each number in the list
22    for current_value in numbers:
23        # Apply the reducer function to the current accumulator and the
24        # current value, then assign the result back to the accumulator.
25        accumulator = reducer(accumulator, current_value)
26
27    # Return the final accumulated value after processing all elements.
28    return accumulator
29
1import java.util.function.BiFunction;
2
3/**
4 * Applies a reducer function on each element of the `numbers` array, resulting in a single output value.
5 *
6 * @param numbers       The array of numbers to be reduced.
7 * @param reducer       The function to execute on each element in the array.
8 * @param initialValue  The initial value to start the accumulation from.
9 * @return The reduced value after all elements have been processed.
10 */
11public static int reduce(int[] numbers, BiFunction<Integer, Integer, Integer> reducer, int initialValue) {
12    // The variable that will accumulate the result of calling the reducer function repeatedly.
13    int accumulator = initialValue;
14
15    // Iterate through each number in the array
16    for (int currentValue : numbers) {
17        // Apply the reducer function to the current accumulator and the current value,
18        // then assign the result back to the accumulator.
19        accumulator = reducer.apply(accumulator, currentValue);
20    }
21
22    // Return the final accumulated value after processing all elements.
23    return accumulator;
24}
25
1#include <vector>
2#include <functional>
3
4// Type alias for the reducer function which is a callback that will be passed to the reduce function.
5// It takes two integers, `accumulator` and `currentValue` and returns an integer.
6using ReducerFunction = std::function<int(int, int)>;
7
8/**
9 * Applies a reducer function on each element of the `numbers` vector, resulting in a single output value.
10 *
11 * @param numbers The vector of integers to be reduced.
12 * @param reducer The function to execute on each element in the vector.
13 * @param initialValue The initial value to start the accumulation from.
14 * @returns The reduced value after all elements have been processed.
15 */
16int reduce(const std::vector<int>& numbers, const ReducerFunction& reducer, int initialValue) {
17    // The variable that will accumulate the result of calling the reducer function repeatedly.
18    int accumulator = initialValue;
19
20    // Iterate through each number in the vector
21    for (int currentValue : numbers) {
22        // Apply the reducer function to the current accumulator and the current value,
23        // then assign the result back to the accumulator.
24        accumulator = reducer(accumulator, currentValue);
25    }
26
27    // Return the final accumulated value after processing all elements.
28    return accumulator;
29}
30
1// Type declaration for the reducer function which is a callback that will be passed to the reduce function.
2// It takes two numbers, `accumulator` and `currentValue` and returns a number.
3type ReducerFunction = (accumulator: number, currentValue: number) => number;
4
5/**
6 * Applies a reducer function on each element of the `numbers` array, resulting in a single output value.
7 * 
8 * @param numbers - The array of numbers to be reduced.
9 * @param reducer - The function to execute on each element in the array.
10 * @param initialValue - The initial value to start the accumulation from.
11 * @returns The reduced value after all elements have been processed.
12 */
13function reduce(numbers: number[], reducer: ReducerFunction, initialValue: number): number {
14    // The variable that will accumulate the result of calling the reducer function repeatedly.
15    let accumulator: number = initialValue;
16
17    // Iterate through each number in the array
18    for (const currentValue of numbers) {
19        // Apply the reducer function to the current accumulator and the current value,
20        // then assign the result back to the accumulator.
21        accumulator = reducer(accumulator, currentValue);
22    }
23
24    // Return the final accumulated value after processing all elements.
25    return accumulator;
26}
27
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Time and Space Complexity

Time Complexity

The time complexity of the reduce function is O(n), where n is the number of elements in the nums array. This is because the function iterates through each element in the array exactly once.

Space Complexity

The space complexity of the reduce function is O(1) as it uses a fixed amount of space. The acc variable is updated during each iteration, but no additional space that grows with the input size is utilized.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫