Array Reduce Transformation

Difficulty: Easy | Acceptance: 85.50% | Paid: No Topics: N/A

Given an array of integers nums, an integer initialValue, and a function fn, return the result of reducing nums using fn.

The reduce function should apply fn cumulatively to the elements of nums, from left to right, starting with initialValue as the first argument.

In other words, the result is defined as follows:

• If nums is empty, return initialValue.

• Otherwise, let result = initialValue.

• For each element num in nums (in order):

  • result = fn(result, num)

• Return result.

• Examples

• Constraints

• Iterative Approach

• Recursive Approach

• Built-in Reduce

Examples

Input: 
  nums = [1,2,3,4]
  fn = function sum(accum, curr) { return accum + curr; }
  init = 0
Output: 10
Explanation:
  initially, the value is init=0.
  - 0 = fn(0, 1) = 1
  - 1 = fn(1, 2) = 3
  - 3 = fn(3, 3) = 6
  - 6 = fn(6, 4) = 10
  The final answer is 10.

Input:
  nums = [1,2,3,4]
  fn = function sum(accum, curr) { return accum + curr * curr; }
  init = 100
Output: 130
Explanation:
  initially, the value is init=100.
  - 100 = fn(100, 1) = 101
  - 101 = fn(101, 2) = 105
  - 105 = fn(105, 3) = 114
  - 114 = fn(114, 4) = 130
  The final answer is 130.

Input:
  nums = []
  fn = function sum(accum, curr) { return 0; }
  init = 25
Output: 25
Explanation:
  For empty arrays, the answer is always init.

Constraints

- 0 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
- 0 <= init <= 1000

Iterative Approach

Intuition Use a simple loop to iterate through the array, applying the function to the accumulator and each element sequentially.

Steps

• Initialize result with initialValue
• Iterate through each element in nums
• Apply fn to result and current element, storing back in result
• Return final result

from typing import List, Callable

def reduce(nums: List[int], fn: Callable[[int, int], int], init: int) -> int:
    result = init
    for num in nums:
        result = fn(result, num)
    return result

Complexity

• Time: O(n) where n is the length of nums
• Space: O(1) only using constant extra space
• Notes: Most straightforward and efficient approach

Recursive Approach

Intuition Process the array recursively by applying the function to the accumulator and first element, then recursively handle the rest of the array.

Steps

• Base case: if array is empty, return init
• Apply fn to init and first element
• Recursively call reduce on remaining elements with new accumulator

from typing import List, Callable

def reduce(nums: List[int], fn: Callable[[int, int], int], init: int) -> int:
    if not nums:
        return init
    return reduce(nums[1:], fn, fn(init, nums[0]))

Complexity

• Time: O(n) where n is the length of nums
• Space: O(n) due to recursion stack
• Notes: Elegant but less efficient due to stack overhead

Built-in Reduce

Intuition Leverage the language’s native reduce/accumulate function to handle the transformation automatically.

Steps

• Call the built-in reduce function with fn, nums, and init
• Return the result

from typing import List, Callable
from functools import reduce as builtin_reduce

def reduce(nums: List[int], fn: Callable[[int, int], int], init: int) -> int:
    return builtin_reduce(fn, nums, init)

Complexity

• Time: O(n) where n is the length of nums
• Space: O(1) for most implementations
• Notes: Most concise and idiomatic, uses optimized built-in functions