Problem Description

You need to implement a reduce function that processes an array of integers using a reducer function and returns a single accumulated value.

The function takes three parameters:

• nums: an integer array to process
• fn: a reducer function that takes two numbers (accumulator and current value) and returns a number
• init: the initial value for the accumulator

The function should work by:

1. Starting with the accumulator set to init
2. For each element in the array (in order), calling fn(accumulator, currentElement) and updating the accumulator with the result
3. Returning the final accumulator value after processing all elements

The process follows this pattern:

• First: val = fn(init, nums[0])
• Then: val = fn(val, nums[1])
• Then: val = fn(val, nums[2])
• Continue until all elements are processed

If the array is empty, simply return init.

The constraint is that you cannot use the built-in Array.reduce method - you must implement the reduction logic yourself using loops or other constructs.

Intuition

The key insight is that reduction is fundamentally about maintaining a running accumulator that gets updated with each element in the array. Think of it like a snowball rolling down a hill - it starts with an initial size (init) and grows by incorporating each element it encounters along the way.

Since we can't use the built-in reduce method, we need to manually replicate what it does internally. The pattern is straightforward: we need to visit each element exactly once, in order, and update our accumulator at each step.

The natural approach is to use a loop that iterates through the array. We need a variable to hold our accumulated value - let's call it acc. We initialize acc with the init value provided. Then, for each element in the array, we apply the reducer function fn with the current accumulator value and the current element, storing the result back in acc.

The beauty of this approach is its simplicity - we're essentially maintaining state (acc) that evolves as we process each element sequentially. After processing all elements, acc contains our final result. If the array is empty, the loop never executes, and we naturally return the initial value, which handles the edge case perfectly.

This mimics exactly what the built-in reduce does under the hood - it's just a controlled iteration with state management, where the state transformation is defined by the provided function fn.

Solution Approach

The implementation follows a straightforward iterative approach:

1. Initialize the accumulator: Create a variable acc and set it to the init value. This serves as our running total that will be updated throughout the iteration.

   let acc: number = init;

2. Iterate through the array: Use a for...of loop to traverse each element in the nums array. This ensures we process elements in order from first to last.

   for (const x of nums) {

3. Apply the reducer function: For each element x, call the reducer function fn with the current accumulator value and the current element. The result becomes the new accumulator value.

   acc = fn(acc, x);

4. Return the final result: After the loop completes (all elements have been processed), return the final value of acc.

   return acc;

The complete flow works as follows:

• If nums = [1, 2, 3], fn = (a, b) => a + b, and init = 0
• Iteration 1: acc = fn(0, 1) = 1
• Iteration 2: acc = fn(1, 2) = 3
• Iteration 3: acc = fn(3, 3) = 6
• Return: 6

The time complexity is O(n) where n is the length of the array, as we visit each element exactly once. The space complexity is O(1) as we only use a single variable to store the accumulator regardless of the input size.

Example Walkthrough

Let's walk through a concrete example to see how the reduction process works step by step.

Example: Sum all elements in an array

• nums = [2, 5, 3]
• fn = (acc, curr) => acc + curr (adds two numbers)
• init = 10

Step-by-step execution:

1. Initialize: Start with acc = 10 (our initial value)

2. First iteration (process element 2):

   • Call fn(10, 2)
   • Result: 10 + 2 = 12
   • Update: acc = 12

3. Second iteration (process element 5):

   • Call fn(12, 5)
   • Result: 12 + 5 = 17
   • Update: acc = 17

4. Third iteration (process element 3):

   • Call fn(17, 3)
   • Result: 17 + 3 = 20
   • Update: acc = 20

5. Return: Final value is 20

The accumulator evolved as: 10 → 12 → 17 → 20

Another Example: Find the product of all elements

• nums = [2, 3, 4]
• fn = (acc, curr) => acc * curr (multiplies two numbers)
• init = 1

Execution trace:

• Start: acc = 1
• After processing 2: acc = 1 * 2 = 2
• After processing 3: acc = 2 * 3 = 6
• After processing 4: acc = 6 * 4 = 24
• Return: 24

Edge Case: Empty array

• nums = []
• fn = (acc, curr) => acc + curr
• init = 100

Since the array is empty, the loop never executes, and we simply return init = 100.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the nums array. The algorithm iterates through each element of the array exactly once, and for each element, it performs a single function call fn(acc, x). Assuming the reducer function fn executes in constant time O(1), the overall time complexity is linear.

Space Complexity: O(1) for the algorithm itself. The function only uses a fixed amount of extra space for the accumulator variable acc and the loop iterator x, regardless of the input size. The space used does not grow with the size of the input array. Note that this analysis assumes the reducer function fn does not use additional space that scales with input size.

Common Pitfalls

1. Mutating the Original Array

A common mistake is accidentally modifying the input array during the reduction process. While the basic implementation shown doesn't have this issue, developers sometimes try to optimize or add features that inadvertently change the original data.

Problematic Example:

def reduce(nums: List[int], fn: Callable[[int, int], int], init: int) -> int:
    accumulator = init
    # Trying to "optimize" by modifying the array
    for i in range(len(nums)):
        nums[i] = fn(accumulator, nums[i])  # DON'T DO THIS - mutates input!
        accumulator = nums[i]
    return accumulator

Solution: Always treat the input array as read-only. Use the current value directly without modifying the array:

def reduce(nums: List[int], fn: Callable[[int, int], int], init: int) -> int:
    accumulator = init
    for current_value in nums:
        accumulator = fn(accumulator, current_value)  # Only update accumulator
    return accumulator

2. Incorrect Handling of Side Effects in the Reducer Function

If the reducer function has side effects or depends on external state, the reduction might produce unexpected results or fail entirely.

Problematic Example:

counter = 0
def problematic_reducer(acc, val):
    global counter
    counter += 1
    return acc + val * counter  # Result depends on external state!

# This will give different results if called multiple times
result1 = reduce([1, 2, 3], problematic_reducer, 0)
result2 = reduce([1, 2, 3], problematic_reducer, 0)  # Different result!

Solution: Ensure the reducer function is pure (no side effects, deterministic):

def pure_reducer(acc, val):
    return acc + val  # Pure function - same inputs always give same output

3. Type Mismatches Between Init and Array Elements

When the initial value type doesn't match what the reducer function expects, it can cause runtime errors or unexpected behavior.

Problematic Example:

# Init is a string, but nums contains integers
def concat_reducer(acc, val):
    return str(acc) + str(val)

# This works but might not be what you expect
result = reduce([1, 2, 3], concat_reducer, "")  # Returns "123"

# This could fail with certain reducers
def multiply_reducer(acc, val):
    return acc * val

result = reduce([1, 2, 3], multiply_reducer, "0")  # TypeError or unexpected result

Solution: Ensure type consistency between init and the expected accumulator type:

# For multiplication, use numeric init
result = reduce([1, 2, 3], multiply_reducer, 1)  # Correct

# For string concatenation, convert appropriately
def safe_concat_reducer(acc, val):
    return str(acc) + str(val)
result = reduce([1, 2, 3], safe_concat_reducer, "")  # Clear intent

4. Not Handling Empty Arrays Properly

While the implementation correctly returns init for empty arrays, developers sometimes forget to test this edge case or make assumptions about non-empty arrays.

Problematic Assumption:

def reduce_with_first(nums: List[int], fn: Callable[[int, int], int]) -> int:
    # Assumes array is non-empty - will crash on empty array!
    accumulator = nums[0]  # IndexError if nums is empty
    for i in range(1, len(nums)):
        accumulator = fn(accumulator, nums[i])
    return accumulator

Solution: Always handle the empty array case explicitly:

def reduce(nums: List[int], fn: Callable[[int, int], int], init: int) -> int:
    if not nums:  # Explicit check (though not necessary with for loop)
        return init
  
    accumulator = init
    for current_value in nums:
        accumulator = fn(accumulator, current_value)
    return accumulator