C++ || O(N) || Easy to Understand with In-Depth Explanation
Table of Contents\n\n- TL;DR\n  - Code\n  - Complexity\n- In Depth Analysis\n  - Intuition\n  - Approach\n  - Example\n\n# TL;DR\n\n Precompute the total sum of
#### Table of Contents\n\n- [TL;DR](#tldr)\n  - [Code](#code)\n  - [Complexity](#complexity)\n- [In Depth Analysis](#in-depth-analysis)\n  - [Intuition](#intuition)\n  - [Approach](#approach)\n  - [Example](#example)\n\n# TL;DR\n\n* Precompute the total sum of all the elements in the arrary\n* Iterate through `nums` and calculate the current average difference\n* If the current average difference is less than the lowest minimum so far, we update the answer and the lowest minimum\n\n## Code\n\n```c++\ntypedef long long ll;\n\nclass Solution {\npublic:\n    int minimumAverageDifference(vector<int>& nums) {\n        const int n = nums.size();\n\n        ll total_sum = 0;\n        for (int i = 0; i < n; i++)\n            total_sum += nums[i];\n\n        int minAvgDiff = INT_MAX, ans = 0, currAvgDiff;\n        ll first_elements, last_elements, currSum = 0;\n        for (int i = 0; i < n; i++) {\n            currSum += nums[i];\n            first_elements = currSum / (i + 1);\n            last_elements = n - i - 1 != 0 ? (total_sum - currSum) / (n - i - 1) : 0;\n            currAvgDiff = abs(first_elements - last_elements);\n            if (currAvgDiff < minAvgDiff) {\n                minAvgDiff = currAvgDiff;\n                ans = i;\n            }\n        }\n\n        return ans;\n    }\n};\n```\n\n## Complexity\n\n**Time Complexity:** $$O(N)$$\n**Space Complexity:** $$O(1)$$\n\n**PLEASE UPVOTE IF YOU FIND MY POST HELPFUL!! \uD83E\uDD7A\uD83D\uDE01**\n\n---\n\n# In Depth Analysis\n\n## Intuition\n\nBy using the brute force approach, you must consistently calculate the sum of elements index $$0 \\rightarrow i$$ and index $$i+1 \\rightarrow n - 1$$. However, by precomputing the prefix sums of every element in O(n), we can calculate the average difference in O(1) time. \n\n**BUT**, we can make the space complexity even better by only computing the sum of all the elements opposed to the prefix sum\n\n## Approach \n\nFirst, we want to calculate the sum of all the elements in the array. Since the total could be greater than what could be stored in an integer, we are using a `long long` instead (type defined as `ll`)\n\nThen, we determine the average of the first `i` elements and last `n - i` elements for every `i` as we iterate. The only weird case is when `n - i - 1 == 0`, which means that the average of the last element is `0`\n\nThen, we just calculate what the current average difference is at index `i` and update the index `ans` and the current `minAvgDiff` if necessary. At the end, we just return the index\n\n## Example\n\nLets use the first example, where `nums = [2,5,3,9,5,3]`\n\n* Calculate total sum\n\nI won\'t actually go over this, but the total sum is 27\n\n* Iterate through Array\n\n|   i  | currSum |         first        |                       last                      | diff | minAvgDiff | ans |\n|:----:|:-------:|:--------------------:|:-----------------------------------------------:|------|:----------:|:---:|\n| Init |    0    |          N/A         |                       N/A                       | N/A  |   INT_MAX  |  0  |\n|   0  |    2    |  $$\\frac{2}{1} = 2$$ |       $$\\frac{(27 - 2)}{(6 - 0 - 1)} = 5$$      | 3    |      3     |  0  |\n|   1  |    7    |  $$\\frac{7}{2} = 3$$ |       $$\\frac{(27 - 7)}{(6 - 1 - 1)} = 5$$      | 2    |      2     |  1  |\n|   2  |    10   | $$\\frac{10}{3} = 3$$ |      $$\\frac{(27 - 10)}{(6 - 2 - 1)} = 5$$      | 2    |      2     |  1  |\n|   3  |    19   | $$\\frac{19}{4} = 4$$ |      $$\\frac{(27 - 19)}{(6 - 3 - 1)} = 4$$      | 0    |      0     |  3  |\n|   4  |    24   | $$\\frac{24}{5} = 4$$ |      $$\\frac{(27 - 24)}{(6 - 4 - 1)} = 3$$      | 1    |      0     |  3  |\n|   5  |    27   | $$\\frac{27}{6} = 4$$ | $$\\frac{(27 - 27)}{(6 - 5 - 1)} \\rightarrow 0$$ | 4    |      0     |  3  |\n\nAt the end, we just return `ans = 3` which is the correct answer\n\n**PLEASE UPVOTE IF YOU FIND MY POST HELPFUL!! \uD83E\uDD7A\uD83D\uDE01**
['Math', 'Prefix Sum', 'C++']