https://leetcode.com/problems/minimum-average-difference/
Language: Python — Time: 35 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

Oddly phrased, but fairly simple challenge. Mostly, this just comes down to recognizing you need to create a prefix sum in order to efficiently generate averages of sub-sums as we iterate through the array. I had a vague memory of learning a data structure that did this implicitly and so challenged myself to use a more advanced DS rather than the obvious solution. After a bit of research I rediscovered the “Fenwick Tree” (wikipedia), a Binary Insertion Tree that stores a prefix array in tree form. This allows a trade off where lookups are O(log n), so quite a bit slower than a prefix sum array, but insertions are also O(log n), where they would be O(n).

I found some example code for implementing a Fenwick Tree (geeksforgeeks) and set to work, knowing full well that this was rather a silly solution: Our given array is static, we will not be performing any future insertions. The benefits of a Fenwick Tree in this scenario is entirely moot. I went this way specifically for the added challenge of implementing a more complicated structure and testing the result. I was quite pleased that it worked exactly as intended, and just squeaked by the minimum requirements for acceptance, being in the bottom 5% for performance.

Another reason I decided to make this harder than it needed to be was to interrupt a habit I’ve noticed I am forming; With the majority of my recent exercises being shortform challenges like Leetcode problem I have fallen into writing in simple block form. I find I opt for iterative solutions instead of writing recursive functions, and I almost never create whole alternate “helper classes” extraneous to the solution. This was a good opportunity to implement the tree structure as its own class, and use that to solve the problem at hand.

Other than this bit of added complication, the solution is a pretty standard “iterate through and note the min” algorithm, using the FenwickTree.getsum() method to calculate the average difference for each index position of our original loop.

I’m glad I took the extra time to further challenge myself on this one. The opportunities to research how more complicated structures work, and how to implement them offer a real chance for growth, and its solutions like this that afford me the best opportunities to grow as a coder.