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 <= 1000This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), for traversing each element.
Space Complexity: O(n), due to recursion stack consumption.
| 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. |
JavaScript Array Reduce • Programming with Mosh • 348,857 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