Given an integer array nums, a reducer function fn, and an initial value init, return the final result obtained by executing the fn function on each element of the array, sequentially, passing in the return value from the calculation on the preceding element.
This result is achieved through the following operations: val = fn(init, nums[0]), val = fn(val, nums[1]), val = fn(val, nums[2]), ... until every element in the array has been processed. The ultimate value of val is then returned.
If the length of the array is 0, the function should return init.
Please solve it without using the built-in Array.reduce method.
Example 1:
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) + nums[0] = 1
(1) + nums[1] = 3
(3) + nums[2] = 6
(6) + nums[3] = 10
The final answer is 10.
Example 2:
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) + nums[0] * nums[0] = 101
(101) + nums[1] * nums[1] = 105
(105) + nums[2] * nums[2] = 114
(114) + nums[3] * nums[3] = 130
The final answer is 130.
Example 3:
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 <= 10000 <= nums[i] <= 10000 <= init <= 1000Problem Overview: You receive an array nums, a reducer function fn, and an initial value init. The task is to repeatedly apply the function so that each array element updates an accumulator value, eventually producing a single final result.
This mirrors how the classic reduce operation works in functional programming. Starting with init, the reducer combines the accumulator with each element in order: acc = fn(acc, nums[i]). After processing every element, the final accumulator value is returned.
Approach 1: Iterative Loop Reduction (O(n) time, O(1) space)
The most direct implementation uses a simple loop. Initialize a variable accumulator with init. Then iterate through the array from index 0 to n-1. For every element, call the reducer function and update the accumulator: accumulator = fn(accumulator, nums[i]). After the loop finishes, return the accumulator.
This approach works because reduction is inherently sequential. Each step depends on the previous accumulator value. The algorithm performs exactly one pass over the array, making the time complexity O(n). Only a single variable is maintained regardless of input size, so the space complexity remains O(1). This pattern appears frequently in problems involving arrays and aggregation tasks such as sums, products, or custom accumulations.
Approach 2: Recursive Reduction (O(n) time, O(n) space)
The same reduction logic can be expressed recursively. Define a recursive function that processes the array index by index. At each step, compute a new accumulator using the current element, then call the function for the next index.
The recursion terminates when the index reaches the end of the array. The final accumulator value is returned back through the call stack. While the algorithm still processes each element once for O(n) time complexity, recursion adds stack frames for every call, resulting in O(n) auxiliary space.
This version is conceptually aligned with functional programming patterns and demonstrates how reduction can be defined in terms of smaller subproblems. It’s a good exercise when practicing recursion or understanding functional abstractions used in languages like JavaScript.
Recommended for interviews: The iterative loop reduction is the expected approach. It is simpler, avoids recursion overhead, and clearly demonstrates how reduction accumulates results across an array. The recursive version still shows strong understanding of functional decomposition, but interviewers generally prefer the iterative implementation because it uses constant space and mirrors real-world implementations of reduce.
This approach simply involves directly iterating through the elements of the array using a loop, starting with the initial value. For each element, apply the reducer function and update the accumulated result. This approach mimics the behavior of the JavaScript Array.reduce method.
In this C implementation, the reduce function takes an array, its size, a function pointer fn, and an initial value. It iteratively processes each element of the array, updating the result with the output of the given function fn. The helper function sum simply adds two integers.
Time Complexity: O(n), where n is the number of elements in the array because we loop through each element once.
Space Complexity: O(1), as we use only a fixed amount of additional space.
This approach employs a recursive strategy to apply the reducer function on each element of the array. By defining a base case for the recursion (i.e., an empty array returns the initial value), the recursion continues until all elements are processed. Care must be taken with recursion due to stack size limitations for large inputs.
The C recursive method reduce_recursive operates by calling itself on the rest of the array, reducing the size each time. The base case returns the initial value when the array is empty. This approach involves plain recursion without stack manipulation.
Time Complexity: O(n), for traversing each element.
Space Complexity: O(n), due to recursion stack consumption.
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Loop Reduction | Time Complexity: O(n), where n is the number of elements in the array because we loop through each element once. |
| Recursive Reduction | Time Complexity: O(n), for traversing each element. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Loop Reduction | O(n) | O(1) | Best general solution. Single pass through the array with constant extra memory. |
| Recursive Reduction | O(n) | O(n) | Useful for learning recursion or functional programming patterns. |
Array Reduce Transformation (Transforms) - Leetcode 2626 - JavaScript 30-Day Challenge • NeetCodeIO • 13,158 views views
Watch 9 more video solutions →Practice Array Reduce Transformation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor