It's algorithm time again!

This one's a leetcode easy, but there's a lot to be learned from it.

Here's the problem:

RANGE SUM QUERY:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

So, if we have an array of, say[1,2,3,4,5], and indices of2 and4, we'd add3 + 4 + 5 to get12.

Pretty simple, right? We can just loop over our array and sum up whatever's between (and including) the indexes we get.

functionNumArr(arr){this.data=arr;}NumArr.prototype.rangeSum=function(i,j){letoutput=0;for(i;i<=j;i++){output+=this.data[i];}returnoutput;}

This is not a horrible solution. If we query our array only once or twice, or if we expect to get in a variety of arrays, this works. Computers are very good at addition-it's possibly the fastest operation a CPU can do. In fact, it's so fast that it actually does pass the leetcode tests.

However, there are two stipulations provided, which give us space to improve and optimize our solution.

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

So, let's think about how this works. If we're doing a sufficient number of sums, some of them will probably hit the same range, right? We can cache our solution and look it up instead of re-calcluating it. Let's put a cache on the constructor.

Caching

What shape should the cache take?
If we think about it for a minute, a two dimensional array seems to make the most sense- we're adding a range fromi toj, so we can dump our cached results atthis.cache[i][j]

functionNumArray(arr){this.data=arr;this.cache=arr.map(()=>[]);//fill cache with one empty array per item in arr}NumArray.prototype.sumRange=function(i,j){if(!this.cache[i][j]){letoutput=0;for(letk=i;k<=j;k++){output+=this.data[k];}this.cache[i][j]=output;}returnthis.cache[i][j];}

This works, but the extra task of storing stuff in our cache makes the initial query to a range much slower. Each successive time we query is gonna be plenty fast, but it also counts on us landing on our exact range again.

Is there an even better solution?

Short answer: yes. very yes.

Getting there was a bit of a pain. Initially, I'd glanced at the leetcode solution and saw something about precomputing the results. I took this to mean that we should pre-calculate and cache the entire thing- and why not?

If we're computing any range sum, we're doing repeated work. i.e. if we sum the values from index0 to index5, we've calculatedarr[0]+arr[1],arr[0]+arr[1]+arr[2], etc etc. This means that we can simply cache some of those intermediary values as we go.

I could intuit that I could at least get the first set of sums like this:

functionNumArray(arr){this.data=arr;this.cache=[]arr.reduce((acc,val)=>{acc+=val;cache.push(val)returnacc;},0)}

When this finishes computing, our cache will be an array with all of the sums from0 ton.[(sum of index 0), (sum of index 0 to index 1), (sum of index 0 to index 2), ...., (sum of index 0 to index n)]

That's a nice little bit of computation that makes our lives easier, but how would we think about getting all of the sums ofindex 1 to index n, thenindex 2 to index n, all the way up toindex n-1 to index n?

I tried to figure out if there was an easy way to compute all possible sums, but kept gettingO(n^2) solutions that would time out on leetcode.

So I tried to figure out what sort of patterns I could see in a test case, modelling it by hand with a very simple array of[0,1,2,3,4]

There are a few interesting things going on. We can see that each successive row is basically made by taking the previous row and subtracting whatever integer we're skipping.

The first row is made by summing all numbers.
The second row can be made by taking the first row and subtracting the first number
The third row can be made by taking the second row and subtracting the second number
The fourth row can be made by taking the third row and subtracting the third number
...and so on.

It took a bit for this to sink in, but the secret here depends on rearranging that previous insight:

In other words, we can find any range fromi toj by taking the sum of numbers from index0 toj, and subtracting the sum of numbers from index0 toi.

With this being the case, all of the data we need is created when we make our initial pass. We're guaranteed to have the appropriate sum for index0 toi, and likewise, for index0 toj. We don't even have to cache every possible answer to have anO(1) operation.

Here's what my final result looks like:

constNumArray=function(nums){this.cache=[0];// done to avoid an "if" check for the first numberfor(leti=0;i<nums.length;i++){this.cache.push(this.cache[i]+nums[i]);}}NumArray.prototype.sumRange=function(i,j){returnthis.cache[j+1]-this.cache[i];}

This saves immensely on time complexity- Our initial pass through the array isO(n), which is the same time complexity as calculating a single range sum in the first place (i.e. if you want to sum from0 toarr.length-1). Afterwards, getting any successive answers is anO(1) operation!

The only real tradeoff is that the space complexity of this solution is alsoO(n), but it's well worth it.