Java | Beats 100% | Prefix Sum | Explained
\n\n# Intuition\nTo calculate the average between range [x:y] in O(1) we can use a prefix sum.\n\nThe sum of an interval [x:y] (inclusive) will be prefix[y] - p
![image.png](https://assets.leetcode.com/users/images/744f5b68-e3d2-498c-b30a-49344e09bd48_1670161849.0439353.png)\n\n# Intuition\nTo calculate the average between range `[x:y]` in O(1) we can use a prefix sum.\n\nThe sum of an interval `[x:y]` (inclusive) will be `prefix[y] - prefix[x-1]` and we would divide by the range of the interval which is `y-x+1` assuming y > x.\n\nTo avoid edge cases while subtracting `prefix[x-1]` we will initialize the array with a buffer of 1, so we can type the code more easily.\n\nNote: the divisor is of type `double` so if we divide by `0d` we don\'t throw a zero division exception.\n\n\n\n# Code\n```\nclass Solution {\n    public int minimumAverageDifference(int[] nums) {\n        int n = nums.length;\n        double[] prefix = new double[n + 1]; // prefix[1] is sum up to i=1 exclusive [0, i)\n\n        // A    =   [2, 3, 5] //\n        // PS   =   [0, 2, 5, 10]\n        for (int i = 0; i < n; i++) {\n            prefix[i + 1] = prefix[i] + nums[i];\n        }\n\n        int bestIndex = 0;\n        int best = Integer.MAX_VALUE;\n\n        for (int i = 0; i < n; i++) {\n            int prefixAverage = (int) Math.floor(prefix[i + 1] / (i + 1));\n            int suffixAverage = (int) Math.floor((prefix[n] - prefix[i + 1]) / (n - i - 1));\n            int averageDifference = Math.abs(\n                    // taking sum up to index i inclusive (i+1 elements)\n                    prefixAverage -\n                    // taking sum from i+1:n (n-i elements)\n                    suffixAverage\n            );\n            if (averageDifference < best) {\n                best = averageDifference;\n                bestIndex = i;\n            }\n        }\n\n        return bestIndex;\n    }\n}\n```
['Java']