Prefix Sums – Alternative explanation to Codility’s

Prefix Sum - P of A


Hello there fellow coder!

This is my explanation of “Prefix Sums” a powerful and versatile algorithm technique.
It can be used for optimizations, parallelization or enabling other algorithms that are essential for all kinds of complex problems.
So it’s a very useful concept to understand, to know where and how to use it. For this post you better be familiar with Big O notation  as I use it to talk about time complexity.

My other motivation was Codility’s material on the subject and how confusing it is. Hopefully my explanation will be clearer than theirs. My code examples are all in JavaScript so you can test it right in your browser.

The concept

Trust me, it’s much easier than it sounds: given a list of numbers A, create a new list P of numbers on which each element is the sum of all the numbers from A prior to its index.

If you are a visual person, this is what it is (A is input and P is the output):

Prefix Sum - P of A
A diagram showing how the Prefix Sum algorithm technique works. P[1] = P[0] + A[1] = 2 + 3 = 5.
If you are a mathematical person, this is what it is:
 Given A = [a<sub>0</sub>, a<sub>1</sub>, a<sub>2</sub>, ... , a<sub>n-1</sub>], of size <i>n > 0</i>
Prefix Sums is
 P = [a<sub>0</sub>, (a<sub>0</sub> + a<sub>1</sub>), (a<sub>0</sub>+a<sub>1</sub>+a<sub>2</sub>), ... , (a<sub>0</sub>+a<sub>1</sub>+ ... + a<sub>n-1</sub>)] 
Or in other words:
P[x] = P[x-1] + A[x]

Like I said, easy huh?

A JavaScript Implementation

There are many ways of implementing this technique but I like this one because is quite readable:

As you can see, its time complexity is linear, O(n). Now that the concept is clear, let’s use it.

Simple Example

Imagine that you have to calculate many many times the sum of parts of an array of numbers. It could be for displaying a heat map or the average stock price. Our example just calculates the sum of all sub-arrays/slices of 5 elements from an initial big array.

The most straight forward way to do it is by repeatedly do the iterative sum as many time as needed. Maybe like so:
The function sumArrayLinear(A, start, end) from the previous Gist can be represented as:
sumArrayLinear(A,x,y): A<sub>x</sub> + A<sub>x+1</sub> + ... A<sub>y-1</sub> + A<sub>y</sub>
And we can apply it like so:
sumArrayLinear([2,3,7,5],1,3): A<sub>1</sub> + A<sub>2</sub> + A<sub>3</sub> = 3 + 7 + 5 = 15
The time complexity of our example is O(n x m). Which is not bad.

But now you have another tool available for your disposal: Prefix Sums.

Let’s put it to use.
We calculate the Prefix Sums array with the numbers array. Then we define a new function which takes the Prefix Sums array as follows:
sumPrefixSumArray(P,x,y): P<sub>y</sub> - P<sub>x-1</sub>
Which basically reads as: The sum of the interval is the sum at the end (y) minus the sum of everything before the start of the interval (x-1). So with just one operation we obtain the result. Its time complexity is constant, O(1). Let’s try with our example.

The Prefix Sum of A = [2,3,7,5] is P = [2,5,12,17] .
sumPrefixSumArray(P,1,3): P<sub>3</sub> - P<sub>1-1</sub> = 17 - 2 = 15
Which is the same result as before, therefore:
A<sub>x</sub> + A<sub>x+1</sub> + ... + A<sub>y-1</sub> + A<sub>y</sub> = P<sub>y</sub> - P<sub>x-1</sub>

We can rewrite our code to use our new function:

The total time complexity is O(n) + m x O(1) which is simply O(n+m). And that’s pretty good! Of course, it all depends on the values of m & n. For our example, the first approach needs roughly 140 operations to obtain the resulting array while the seconds needs only 61.


There you have it!
The Prefix Sums technique for all sorts of other more complex problems. A powerful simple idea.
Was I clear? Spotted any problems or bugs? Do you know other examples where Prefix Sums can be used? Speak up on the comments bellow.


5 thoughts on “Prefix Sums – Alternative explanation to Codility’s”

  1. I enjoyed the explanation, especially the combination of visual, code and the math, but I still have a problem where or when would I use this? A finished project to show it in, would be great!

    1. Hi Alex! I’m glad that you enjoyed it and your questions is indeed the ultimate question and the answer is: anywhere you see fit! Like I mentioned on the beginning of the post, some much-clever-than-me people has used the Prefix Sums technique in amazing aways. You can read the Wikipedia page for more concrete examples. I could see it being used to calculate the current Traffic on roads and displaying it on a map. Cheers!

  2. Thanks for explanation. You are correct that the codility explanation is less than illuminating – it follows an all-too-common pattern I run across in tech writing: it makes perfect sense if the reader already knows it. This was much easier to follow and work with.

    1. You are welcome Jordan! I’m glad that my explanation was easier to understand. Cheers!

  3. Great job!
    Your explanation is thousand times better than codility one 🙂
    thank you!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.