Table of contents
Another Medium category problem which I had a lot of fun solving. The fourth problem of the December leetcoding challenge https://leetcode.com/problems/minimum-average-difference/ is another way to flex your array skills. This challenge tests how you can efficiently use arrays to come up with an elegant solution, notably, we will see how prefix arrays help us do so. Even though I could come up with the solution on my own but it was only because I was familiar with using prefix arrays from my previous failed attempts while solving other problems. It may not be the case if you are just learning about them. Anyhow, let's find out what they are and how using them would solve this problem efficiently.
Problem breakdown
We are given a 0-indexed array and we need to calculate the average difference of every index. They defined the average difference being the absolute difference between the first i+1 elements and the last n-i-1 elements. Then return the index where the average difference is the least. Pay attention to the words first and last and you will notice that for calculating the first i+1 elements you need to go forward in the array or move rightwards and for the last elements, we need to calculate backward in the array.
My approach
This problem comes off as an array traversal problem and indeed as a naive approach, we can copy the original array to save as a reference to original elements and take two additional arrays where we save the results of the forward pass and in another the results of the backward pass. Then simply calculate the difference between the arrays and return the index of the element being the minimum.
Good enough approach but can we do better than using those extra spaces since it will be a problem as soon the length of the array increases? We shall now try to overcome this problem using prefix sums. Look carefully at our previous approach and you will notice that we are calculating the sum of the desired segments twice for each iteration for which we needed the extra spaces. If we can somehow save the total sum of the required segments and reuse them for the next backward iteration, we can avoid the extra spaces.
Prefix-array
prefix arrays can save us this trouble as we can calculate the sum of elements seen so far and traverse the array in one pass. Suppose we are given the array
[1,2,3,4,5]
then if you go forward one step and add the current element to the previous element and keep doing so, you will get an array like this [1, 3, 6, 10, 15] . Notice that at each index, we have stored the sum of elements seen till that index. This is called the prefix sum and this kind of array that does so is called a prefix array. The cool thing is the last element of this array is the total sum of all the elements in the array. So we can utilize these features to our advantage and avoid using extra arrays altogether.
def minimumAverageDifference(self, nums: List[int]) -> int:
n = len(nums)
#prefix array calculation
for i in range(1, n):
nums[i] = (nums[i-1] + nums[i])
totalSum = nums[n-1]
# performing the backward pass and average calculation in a single step
for i in range(n-1):
nums[i] = abs((nums[i]//(i+1))-((totalSum-nums[i])//(n-i-1)))
#I performed the calculation for the last element since n-i-1 becomes zero and we cannot perform division by zero
nums[n-1] = totalSum // n
return nums.index(min(nums))
After calculating the prefix sum we can avoid the backward pass by realizing that the sum of the last n-i-1 elements of each index is simply the total sum that we know from the prefix array minus the current element. Takes a while to figure out at first but you can't unsee it after you've learned the prefix array approach.
Time and Space complexity
The overall time complexity should be O(n) since we traverse the array twice separately once for calculating the prefix sum and then the second time for calculating the averages.
The space complexity is O(1) here as we have avoided using any extra spaces.
That's a wrap for today and feel free to share your solution as well.