Introduction

In this post, I will share the implementation of the prefix and suffix sum of an array. I searched a lot to find the implementation of prefix and suffix in python before writing this article but I didn't get exactly what I wanted. Somehow I figure it out. So, I explaining all I learned to implement that concept in python.

Prefix Sum

The prefix is the sum of all elements of the given array/list till ith index from the beginning. We will create an array/list and initialize all indexes by 0. And we iterate the original array/list (which holds the actual elements) one by one and we add an ith element with i+1 element.

Here is an example:

arr = [4, 3, 8, -9, 1]
P[0] = 4, P[1] = 7, P[2] = 15, P[3] = 6, P[4] = 7
Therefore, The sum of the prefix = [4, 7, 15, 6, 7]

Implementation of prefix sum in python

# Python  implementation of the Prefix Sum

# Function to fill prefix_sum array
def fill_prefix_sum(arr, length_arr, prefix_sum):
    prefix_sum[0] = arr[0] 

    for i in range(1, length_arr): # 1, 2, 3, 4
        prefix_sum[i] =  prefix_sum[i-1]+ arr[i] 

# Driver code
arr = [4, 3, 8, -9, 1]
length_arr = len(arr)

prefix_sum = [0 for i in range(length_arr)]  # [0, 0, 0, 0]
print(prefix_sum)

fill_prefix_sum(arr, length_arr, prefix_sum)

for i in range(length_arr):
    print(prefix_sum[i], " ", end="")

Suffix sum

The suffix is the sum of all elements of the given array till ith index from the end. This is also the same as prefix sum but the main difference is we add from the end. Or iterate it from the end.

Here is an example:

arr = [4, 3, 8, -9, 1]
P[0] = 7, P[1] = 3, P[2] = 0, P[3] = -8, P[4] = 1
Therefore,  The sum of siffix = [7, 3, 0, -8, 1]

Implementation of suffix sum in python

# Python implementation of the Suffix Sum
def fill_suffix_sum(arr, length_arr, suffix_sum):
    suffix_sum[length_arr-1] = arr[length_arr-1] 

    for i in reversed(range(length_arr-1)): # 3, 2, 1, 0
        suffix_sum[i] = suffix_sum[i+1] + arr[i]
        print(i, " ", suffix_sum[i]) 

#Driver code
arr = [4, 3, 8, -9, 1]

length_arr = len(arr)

suffix_sum = [0 for i in range(length_arr)]  # [0, 0, 0, 0, 0]
print(suffix_sum)

fill_suffix_sum(arr, length_arr, suffix_sum)

# Printing fill suffix sum array
for i in range(length_arr):
    print(suffix_sum[i], " ", end="")

Conclusion

The implementation for prefix and suffix of an array/list is useful for solving competitive programming questions like sum of an infinite array, calculating maximum sum subarray, etc.

For prefix, iterate loop from the beginning, and for suffix iterate loop from the end. And print using the loop as well.

I hope this article is helpful for you, let me know your opinion about this article via DMs or write to my Gmail (sailendra9083@gmail.com)