Prefix Sum

Learn via video course
FREE
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Topics Covered

Overview

Given an array arr of size n, the prefix sum is another array (say prefixSum) of same size such that for each index 0 <= i < n prefixSum[i] denotes a[0] + a[1] .... + a[i].

Takeaways

While traversing the array, update the element by adding it with its previous element.

Problem Statement

Given an integer array arr of size n, return an array of the same size where the value stored at the ithi^{th} index of this newly formed array denotes the sum of the subarray of arr that starts from the 0th0^{th} index and ends at the ithi^{th} index.

Example

Input : a[] = {3, 2, 1, 5, 4}
Output : prefixSum[] = {3, 5, 6, 11, 15}
Explanation : The below given table shows, how the prefixSum array can be created using the given array.

iCalculationprefixSum[i]
033
13 + 25
23 + 2 + 16
33 + 2 + 1 + 511
43 + 2 + 1 + 5 + 415

Solution

Brute Force Approach

One of the brute force approach to construct the prefixSum array is, for each index i compute the the value of a[0] + a[1] + ... + a[i], and store the result in prefixSum[i].

The pseudocode of this approach is -

So, we are done, we have seen the algorithm and code and now we are good to go. If you are thinking the same, please go through the pseudocode again and try to determine its time complexity.

The time complexity of this approach is O(n2)O(n^2), which can be easily optimized to O(n)O(n) by using the simple trick described in the next section.

Efficient Approach

Intuition

Before discussing the efficient approach, let us first see the simple mathematics required to build intuition toward this approach. Let's say we need to find the sum of elements x1+x2+...+xnx_1 + x_2 + ... + x_n and due to some reason we already calculated the sum of x1+x2+...+xn1x_1 + x_2 + ... + x_{n-1} in the past. Now we have two options -

  1. Calculate the sum of all elements again.
  2. Or use the associative property of addition i.ei.e - 1nxi=(1n1xi)+xn\sum_1^n x_i = (\sum_1^{n-1} x_i )+ x_n

Obviously the latter requires much fewer calculations as we already have the value 1n1xi\sum_1^{n-1} x_i and we just need to add xnx_n to it to obtain the desired result.

Now, let's see how we can use this to find the prefix sum efficiently.

Algorithm

It can noticeable that, prefixSum[0]=a[0]prefixSum[0] = a[0] in all cases because it is the first element. And, for all other indices i the prefix sum can be calculated using the formula prefixSum[i]=prefixSum[i1]+a[i]prefixSum[i] = prefixSum[i-1] + a[i] because while calculating the prefixSum[i1]prefixSum[i-1] we already had calculated a[0]+a[1]+...+a[i1]a[0] + a[1] + ... +a[i-1]. Therefore, to calculate the prefixSum[i] i.e. a[0]+a[1]+...+a[i]a[0] + a[1] + ... + a[i] we just need to add a[i] in prefixSum[i1]prefixSum[i-1].

The steps required in the algorithm is as follows -

  • Declare an array prefixSum of size n with all its entries initialized to 0.
  • Assign a[0] to prefixSum[0].
  • Iterate from i = 0 to i = n - 1 and do the following -
    • Store the value of prefixSum[i-1] in a varaible (say prev).
    • Assign the value prev + a[i] to prefixSum[i].
  • Return prefixSum.

Java Implementation

Output -

C++ Implementation

Output -

Python Implementation

Output -

Complexity Analysis

Time Complexity - Since, we are traversing the array only once, which requires O(n)O(n) steps. Therefore, the time complexity is O(n)O(n).

Space Complexity - An array of size nn is required to store the answer. Therefore the space complexity is O(n)O(n).

How to Calculate the Sum from l to r using Prefix Sums?

Suppose that due to some reasons, we need to compute multiple range sum queries sum[l,r]sum[l, r]. Where sum[l,r]sum[l, r] means sum array elements whose indices are in range [l,r][l, r] i.e.i.e. a[l] + a[l+1] + ... + a[r]. The brute force method is to find the sum using the for loop, which costs O(n)O(n) time per query. While the efficient method uses the prefixSum array to answer each query in constant time. Let's see how -

Let's say we have an query sum[l,r]sum[l, r], now we know that prefixSum[r]=a[0]+a[1]+...+a[r]prefixSum[r] = a[0] + a[1] + ... + a[r] and prefixSum[l1]=a[0]+a[1]+...+a[l1]prefixSum[l-1] = a[0] + a[1] + ... + a[l-1]
Now, if we calculate prefixSum[r]prefixSum[l1]prefixSum[r] - prefixSum[l - 1]
i.e. a[0]+a[1]+...+a[l]+..+a[r](a[0]+a[1]+...+a[l1])a[0] + a[1] + ... + a[l] + .. + a[r] - (a[0] + a[1] + ... + a[l - 1]), we obtain the required answer i.e. a[l]+a[l+1]...+a[r]a[l] + a[l + 1] ... + a[r]

The steps required to find are -

  1. Let's say we have constructed the prefixSum array.
  2. For each query range sum query sum[l,r]sum[l, r] do the following -
    • If l = 0, simply return prefixSum[r].
    • Otherwise return prefixSum[r] - prefixSum[l - 1].

Java Implementation

Output -

C++ Implementation

Output -

Python Implementation

Output -

Complexity Analysis

Time Complexity - If the size of the array is nn and we need to answer qq queries, the time complexity is O(n+q)O(n + q). Where O(n)O(n) is required in the construction of prefixSum and O(1)O(1) time required to answer each query.

Space Complexity - Since, we require an array of size nn to store the prefixSum the space complexity of the solution is O(n)O(n).

Use Cases and Application of Prefix Sum

  • Equilibrium index of an array - The equilibrium index can be defined as the index in the array such that the sum of elements of lower indices is equal to the sum of elements of higher indices. This can easily be found by traversing the prefixSum array once and for each index i checking if the sum of range [0, i] is equal to the sum of range [i+1, n - 1].

  • Find if there exists a subarray with sum 0 - Given an array consisting of integers (possibly negative integers). Check if there exists a non-empty subarray such that the sum of elements in it is 0. This can be checked using the prefixSum and some simple hashing concepts.

  • Find the minimum farthest checkpoint reachable - Given a card with a certain amount of fuel, find the farthest reachable approach if it costs 1 unit of fuel in covering 1 unit of distance. The brute force apporach requires O(n)O(n) time, while if we use the concept of prefixSum and binary search it can be optimized to O(logn)O(\log{n}).

Conclusion

  • Prefix sum is the array constructed based on the values of another array (provided as input).
  • Each index of prefixSum array contains the sum of elements of the subarray that starts at the 0th0^{th} index and ends at ithi^{th} index.
  • The concept of prefix sum can be used in solving a variety of problems efficiently.

FAQs

Q. What Should be Done if we have Quite Large Values given in the Array?

A. In such cases, it is advisable to declare prefixSum array such that it can hold 64-bit integers. This is done so that values do not overflow.

Q. Is there any PrefixSum for a 2-D Array?

A. Yes, there exists prefixSum for 2-D arrays also. They are represented as 2-D array, where prefixSum[i][j] consists of sum of all elements a[x][y] such that 0 <= x <= i and 0 <= y <= j.