Prefix Sum

Concept

The array sum at every given index is pre-calculate by iterating through the array

Normal Array --> [1 2 3 4 5]

Prefix Array --> [1 3 6 10 15]

Prefix operations

• A[] → Normal Array

• B[] → Prefix Array

Initial → preSum[0] = nums[0]

preSum[i] = preSum[i-1] + A[i], where i > 0

This approach works because, when storing the prefix sums, we have the sum available at that point.

$$sum[i,j] = sum[0,j] -sum[0, i-1], where\:i < j$$

<target> = <sum till j> - <sum till i>

The reason for subtracting is since we are maintaining a prefix sum, we already have the sum of the sub-array till the point j. The point i contains the sum till

Full Array with presum

Let's consider in the above table, we want to get the sum of the subarray from [1,2]

Calculating subarray sum from indices [1,2]

Looking at it, we can understand that the sum of the given subarray is 5. How we can derive it in the following way

Explaination of calculation

So in the code, when we find the complement in the preSum, it means that a ranged query/subarray contains the required target.

Type of problems

This technique can be applied in cases of arrays mainly. The Prefix Sum technique can be used when the sliding window does not seem to work, like the problem does not get a proper condition to shrink or expand the window.

• Sub array problems

• Ranged sums

• Equilibrium index → Sum of left side == sum of right side

• Subarray with 0 sum

• Maximum subarray size, such that all subarrays of that size have sum less than k

• Maximum occurred integer in n range

• Exactly "k" number of integers = atmost(k)-atmost(k-1)

Practice Problems:

• https://leetcode.com/list/epvy5cd2

• Prefix Sum Problems - LeetCode Discuss

References:

• Prefix Sum Array - Implementation and Applications in Competitive Programming - GeeksforGeeks

• C++| Full explained every step w/ Dry run | O(n^2) -> O(n) | Two approaches → Clear cut explanation

• General summary of what kind of problem can/ cannot solved by Two Pointers

• https://leetcode.com/problems/subarrays-with-k-different-integers/solutions/235235/C++Java-with-picture-prefixed-sliding-window/