Data Structures and Algorithms — Prefix Sum Technique

We will examine the prefix sum technique in this article and learn how to use it because it reduces the time complexity from O(n ²) to O(n). The only point is that we can use it for only integer arrays.

Let’s say we try to find the sum of any subarray of an integer array, if we try to do it using nested for loop, there will be a time complexity of O(n ²), however, we can find it in O(1) with the prefix sum technique.

Creating prefix sum array will have a time complexity O(n)

int[] array = { 1, 2, 3, 4 };

// this is how we create the prefix sum array
int[] prefixSum = new int[array.Length];
prefixSum[0] = array[0];

for (int i = 1; i < array.Length; i++)
{
    prefixSum[i] = prefixSum[i - 1] + array[i];
}


Console.WriteLine("Before Prefix");
foreach (var item in array)
{
    Console.Write(item + " ");
}

Console.WriteLine("\nAfter Prefix");
foreach (var item in prefixSum)
{
    Console.Write(item + " ");
}

If you want to find the length of the subarrays, you can use the formula of n*(n+1)/2 where n is the length of the array

Let’s check some examples

Running Sum of 1d Array (Easy Level)

Running Sum of 1d Array - LeetCode

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

We can use the prefix sum technique to solve the problem. Only we need to implement the logic.

  for(int i=1;i<nums.Length;i++)
  {
      nums[i] = nums[i-1]+nums[i];
  }
  
  return nums;

Minimum Value to Get Positive Step by Step Sum(Easy Level)

Minimum Value to Get Positive Step by Step Sum - LeetCode

Given an array of integers nums, you start with an initial positive value startValue. In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right). Return the minimum positive value of startValue such that the step by step sum is never less than 1.

We can find the result using the prefix sum technique in this question and the time and space complexity will be O(n).

First, we need to create the prefix sum array

int[] prefixSum=new int[nums.Length];
prefixSum[0]= nums[0];

for(int i=1;i<nums.Length;i++)
{
    prefixSum[i] = prefixSum[i-1] + nums[i];
}

The second step will be to find the minimum value of the array because we need to find a value that never makes a sum less than 1. For example, if our min value is 4, we can say that 5 is the value that we are looking for because it will be never less than 1 once we subtract 5 from 4.

int minValue=0;
for(int i=0;i<prefixSum.Length;i++)
{
    if(prefixSum[i] < minValue)
    {
        minValue = prefixSum[i];
    }
}

then return the value, we use Math.Abs function because the minValue could be less than zero and we do not want it. (Because we try to find the value that is bigger than minValue)

return Math.Abs(minValue)+1;

All code is like the one below

int[] prefixSum=new int[nums.Length];
prefixSum[0]= nums[0];

for(int i=1;i<nums.Length;i++)
{
    prefixSum[i] = prefixSum[i-1] + nums[i];
}

int minValue=0;
for(int i=0;i<prefixSum.Length;i++)
{
    if(prefixSum[i] < minValue)
    {
        minValue = prefixSum[i];
    }
}

return Math.Abs(minValue)+1;

I tried to explain the prefix sum technique in this article because it is an efficient way to reduce the time complexity in the case of the sum of subarrays.

You can reach out to the code here.