Algorithms: Range Sum Query

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 of 2 and 4, we'd add 3 + 4 + 5 to get 12.

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

function NumArr(arr){
  this.data = arr;
}

NumArr.prototype.rangeSum = function(i, j){
  let output = 0;
  for(i; i<=j;i++){
    output+=this.data[i];
  }
  return output;
}

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 from i to j, so we can dump our cached results at this.cache[i][j]

function NumArray(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]){
    let output = 0;
    for(let k = i; k<=j;k++){
      output+=this.data[k];
    }
    this.cache[i][j] = output;
  }
  return this.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 index 0 to index 5, we've calculated arr[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:

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

When this finishes computing, our cache will be an array with all of the sums from 0 to n. [(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 of index 1 to index n, then index 2 to index n, all the way up to index n-1 to index n?

I tried to figure out if there was an easy way to compute all possible sums, but kept getting O(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 from i to j by taking the sum of numbers from index 0 to j, and subtracting the sum of numbers from index 0 to i.

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 index 0 to i, and likewise, for index 0 to j. We don't even have to cache every possible answer to have an O(1) operation.

Here's what my final result looks like:

const NumArray = function(nums){
  this.cache = [0]; // done to avoid an "if" check for the first number
  for (let i = 0; i < nums.length; i++){
    this.cache.push(this.cache[i]+nums[i]);
  }
}

NumArray.prototype.sumRange = function(i,j){
  return this.cache[j+1]-this.cache[i];
}

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

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