Prefix Sum

Hello, today’s topic is back at it again with the algorithms blog. Today we are going to talk about leetcode question #724 Find Pivot Index. Before we are trying to solve the question, we should understand what prefix sum is.

What is the Prefix Sum?

Prefix sum in the array is iterating through index 1 to last and adding the present element with the previous value. People also called this term cumulative sum, inclusive scan, or scan of the sequence number. The intuition behind this is that the prefix array’s previous position will have the previous elements' sum. In that way, we can find the total sum up to a certain point by checking the prefix sum array’s value. We don’t need to go through each time to know the value between two positions in the array with a prefix sum array. We can be efficient with our code to calculate from the values in the prefix sum array.

Now that we know what prefix sum is, let’s solve this question.

Here is the question:

https://leetcode.com/problems/find-pivot-index/

To solve this question, we can get the total sum of all values from the left to right index. Once we get the total sum, we can get the right and left sum under one loop to meet the condition. With the left sum, we can do the normal prefix sum from left to right index cumulative sum to get the left sum. If we know the left sum left to index i, then we can get the right sum with the total sum minus the left sum and the current index that we are iterating through. You can check the code down below for further detail.

Solution

As you can see, we only need to know the prefix sum of the array to get the left and right sum.

So there you go, that is the prefix sum. I hope you enjoy reading it!