Prefix Sums – Alternative explanation to Codility’s

Intro

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 = [a0, a1, a2, ... , an-1], of size n > 0
Prefix Sums is
 P = [a0, (a0 + a1), (a0+a1+a2), ... , (a0+a1+ ... + an-1)] 
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): Ax + Ax+1 + ... Ay-1 + Ay
And we can apply it like so:
sumArrayLinear([2,3,7,5],1,3): A1 + A2 + A3 = 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): Py - Px-1
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): P3 - P1-1 = 17 - 2 = 15
Which is the same result as before, therefore:
Ax + Ax+1 + ... + Ay-1 + Ay = Py - Px-1

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.

Fin

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.

Cheers!

Flattr this!