Prefix Sum

Main Source:

Prefix sum — Wikipedia

Prefix Sum, also known as cumulative sum, is the a sequence where each element is the sum of all the element before it, including itself.

A prefix is something placed before another. For instance, a prefix of an array of given element is all the element that comes before it. When we have array: [1, 4, 5, 7], the prefix of element 5 is 1 and 4. The prefix sum of this array would be another array with the same size, where each element is the sum up to each of the element itself in the original array.

Here is an illustration:

So the prefix sum of the array [1, 4, 5, 7] is [1, 5, 10, 17]. Notice that the last element in the prefix sum is the entire sum of the array itself.

Sum of K First Elements

The objective of this problem is to calculate the sum of the first K elements in an array. Given an array [1, 4, 5, 7], if we have a value of K equal to 2, we need to return the sum of the first two elements. In this case, the first two elements are 1 and 4, and their sum is 5. Hence, when K is 2, the expected result is 5.

The complexity of this problem increases when we introduce multiple values of K. In addition to the original array, we are now given an array of K that contains varying numbers.

Input:
arr = [1, 4, 5, 7]
k = [0, 2, 3, 1]

Output:
result = [0, 5, 10, 1]

Explanation:

For k = 0, the sum is 0 (no elements considered).
For k = 2, the sum is 1 + 4 = 5 (considering the first two elements).
For k = 3, the sum is 1 + 4 + 5 = 10 (considering the first three elements).
For k = 1, the sum is 1 = 1 (considering the first one elements).

Naive Solution

The pseudocode for this:

function sumKElements(arrayOfNumber, arrayOfK)
    result = []
    sum = 0

    for each k in arrayOfK:
        for the first k element in arrayOfNumber:
            sum = sum + element
        append sum to result
        sum = 0

    return result

We would sum up to K for each K in the arrayOfK. While this is a correct solution, it is very inefficient. As we can see in the explanation above, we did a lot of repeated work. For example, when we calculate k = 3, we would need to add 1 + 4 + 5. When we calculate k = 2, we would need to add 1 + 4.

The worst case scenario occurs when we got an array of K, where each K is a large number, making us need to sum the whole array again at each K. The worst-case scenario time complexity for this algorithm would be $O(n * k)$ , where $n$ is the length of the array and $k$ is the length of the array of K.

Prefix Sum Approach

This problem can be optimized using prefix sum approach. We will first generate the prefix sum array, and then we can just return the prefix sum array at index k - 1 (we subtract with 1 because array index starts from 0) for each K in the arrayOfK easily.

function sumKElements(arrayOfNumber, arrayOfK)
    result = []
    prefixSum = [0]

    for each number in arrayOfNumber:
        lastSum = get last element of prefixSum
        currentSum = lastSum + number
        add currentSum to prefixSum

    for each k in arrayOfK:
        add prefixSum[k] to result

    return result

Here is the illustration:

To generate a prefix sum, you iterate through the array of numbers and at each iteration, add the current element to the sum accumulated so far. We will initially put 0, indicating we have accumulated 0 so far. The result of each sum is appended to the prefixSum array, where each element represents the cumulative sum of the arrayOfNumber up to that specific element's index.

Generating prefix sum basically iterate the whole array, it takes $O(n)$ time, where $n$ is the length of the arrayOfNumber. The iteration of arrayOfK will result in $O(k)$ , where $k$ is the length of the arrayOfK. With both iteration together, this results in $O(n + k)$ time complexity

Sum of K First Elements​

Naive Solution​

Prefix Sum Approach​

Sum of K First Elements

Naive Solution

Prefix Sum Approach