[Fully Explained] O(N) 😱+ array.reduce() with bakery example 🍰✅+Flow Diagram+Why array.reduce()?🤔
Introduction \n\nIn this problem, we are given an array nums, a reducer function fn, and an initial value init. We need to return a reduced array by applying th
# Introduction \n\nIn this problem, we are given an array `nums`, a reducer function `fn`, and an initial value `init`. We need to return a reduced array by applying the given operation on every element of the input array, starting from the initial value.\n\nWe need to solve this problem without using the built-in `Array.reduce()` method. In this solution, we will discuss an approach to solve this problem and the reasons why we should use the `array.reduce()` method instead of the corresponding brute force array transformation.\n\n# How does array.reduce() work?\n\nThe `array.reduce()` method in JavaScript is a powerful tool that can be used to perform a wide range of operations on arrays. The method takes a reducer function as an argument and applies it to each element in the array, resulting in a single, accumulated value.\n\nTo understand how `array.reduce()` works, let\'s consider a real-life example. Imagine that you are organizing a bake sale for a charity event. You have a list of baked goods and their corresponding prices that you want to sell, and you need to calculate the total amount of money that you expect to raise from the sale.\n\n![](https://media.giphy.com/media/DZXgs2OSwOqGY/giphy.gif)\n\nOne way to do this is to use the `array.reduce()` method. You can create an array of the prices of each baked good, and then use the method to add up all the prices to get the total amount.\n\nHere is an example implementation in JavaScript:\n\n```javascript\nconst bakedGoods = [\n  { name: \'Chocolate Chip Cookies\', price: 2.50 },\n  { name: \'Cupcakes\', price: 3.00 },\n  { name: \'Brownies\', price: 2.00 },\n  { name: \'Lemon Bars\', price: 2.50 }\n];\n\nconst totalAmount = bakedGoods.reduce((acc, item) => acc + item.price, 0);\n\nconsole.log(totalAmount); // Output: 10.00\n```\n\nIn this example, we have an array `bakedGoods` that contains four objects, each representing a baked good and its price. We use `array.reduce()` to iterate through the array and add up all the prices, starting from an initial value of 0. The reducer function takes two arguments: an accumulator `acc`, which is the accumulated value from the previous iteration, and the current `item` in the array. We add the price of the current `item` to the accumulator and return the updated accumulator value.\n\nThe final result of `array.reduce()` is the total amount of money that we expect to raise from the bake sale.\n\n# Approach to Solve the Problem \n\nIn this problem, we need to apply a reducer function on each element of the input array, starting from the initial value, until we have processed every element of the array. We can implement this logic using a `for-loop` or a `forEach()` method.\n\nHowever, since we are not allowed to use the built-in `array.reduce()` method, we will use a loop to iterate through the input array and apply the reducer function on each element. We will store the intermediate results in a new array and return the final element of this array as the answer.\n\nHere is a flow diagram of this approach:\n\n![](https://res.cloudinary.com/dzy4r0fgy/image/upload/v1683700427/Untitled-2023-02-28-0954-28_g4dnfb.png)\n\nLet\'s implement this approach in JavaScript:\n\n## Code\n```\n/**\n * @param {number[]} nums\n * @param {Function} fn\n * @param {number} init\n * @return {number}\n */\nvar reduce = function(nums, fn, init) {\n    let len = nums.length;\n    if(len==0) return init;\n    let newArr = [];\n    nums.forEach((element,index)=>{\n        newArr[index] = index == 0 ? fn(init,nums[index]) : fn(newArr[index-1],nums[index]);\n    })\n    return newArr[len-1];\n};\n```\n\n\n# Complexity Analysis\n\n- The **time complexity** of this code is **O(n)**, where n is the length of the `nums` array, because the code iterates through the `nums` array once using the `forEach()` method, which has a time complexity of O(n). Inside the `forEach()` method, each operation is constant time, so the total time complexity is O(n).\n\n- The **space complexity** of this code is **O(n)**, where n is the length of the `nums` array, because a new array `newArr` is created with the same length as `nums`. Therefore, the space required by this algorithm increases linearly with the size of the input `nums` array. Additionally, the space complexity does not depend on the size of the `init` parameter, since it is a constant size.\n\n# Why do we use array.reduce() and not its corresponding brute force transformation?\n\n- The `array.reduce()` method provides a simple and elegant way to reduce an array to a single value. It is a higher-order function that abstracts away the details of iteration and accumulation of values, and allows us to focus on the reducer function.\n\n- Using a brute force array transformation requires us to write more code and handle the iteration and accumulation of values ourselves. It can also be error-prone and harder to read, especially for more complex operations.\n
['JavaScript']