The prefix sum array problem

What is the prefix sum array problem?

The prefix sum problem in computer science is a popular programming puzzle used to test the array handling skills of software developers.

The prefix sum problem can be stated as follows:

“Given an array of numbers, create a second array where each element stores a running total calculated from adding the corresponding element in the first array.”

Here is a simple example of a prefix sum created from an original array of digits:

Original Values

10

20

12

28

10

19

101

799

Prefix Sums

10

30

42

70

80

99

200

999

Prefix sum approaches in Java

In modern software development languages such as Java, Python and Mojo, the prefix sum problem can be solved through two very different approaches:

1. The traditional, slow brute-force approach that uses loops and arrays.
2. A high-performance approach that uses advanced Vector and single instruction multiple data (SIMD) semantics.

In this article we’ll explore the traditional approach to the prefix sum problem in Java. In a follow-up article we’ll solve the problem with the Java Vector API.

How to solve the prefix sum problem

Follow these steps to quickly and easily solve the prefix sum array problem in any programming language:

1. Declare a variable to hold the initial values.
2. Declare a second array whose size is the same as the first.
3. Set element zero of the second array equal to element zero of the first.
4. Loop through the original array, starting at element 1.
5. On each iteration, update the current element of the summed array to the running total. To do this, add the previous element of the summedArray to the current element of the originalArray.

Prefix sum example in Java

The prefix sum Java solution looks as follows:

// The original values to be used stored in an array
int originalArray[] = { 10, 20, 12, 28, 10, 19, 101, 799 }; 
// Hold the prefix sum in a second array named summedArray
int summedArray[] = new int[originalArray.length]; 
// The first element of each array will be the same
summedArray[0] = originalArray[0]; 

// Calculate the prefix sum in a loop that starts at 1
for (int i = 1; i < originalArray.length; i++) 
  summedArray[i] = summedArray[i - 1] + originalArray[i]; 

// Print the original array and the Java prefix sum solution
System.out.println(Arrays.toString(originalArray));
System.out.println(Arrays.toString(summedArray)); 

[10, 20, 12, 28, 10, 19, 101, 799]
[10, 30, 42, 70, 80, 99, 200, 999]

Prefix sum optimization

This solution is simple and elegant, but it is not optimized for maximum efficiency.

The new Java Vector API that is currently in the incubation stage enables multiple operations to take place on an array of values at the same time using CPUs that support SIMD operations. This can greatly reduce the number of clock cycles required to solve a puzzle like this when it becomes computationally intensive.

Maxim Zaks demonstrated a SIMD approach to solve this puzzle in the Mojo programming language. Stay tuned to see how to use a similar approach to solve this problem using the Java Vector API.