Home » Interview coding problems/challenges

All subarray Sum of an array

In this article, we are going to see how to find all the subarray sums of an array? This is an interview problem can be featured in an interview round. Submitted by Radib Kar, on September 02, 2019

Problem statement

Find sum of all subarray sums out of an array.

Example:

    Input array: 
    [1, 2, 3, 4]
    
    Output:
    50

Solution:

Of course, there exists an easy solution where we can use three for loops with time complexity (O (n3)). The outer loop and intermediate loop are to iterate through all subarrays and the innermost one is to compute the sum. But here, we are not going to discuss this simple brute-force solution. Rather we will discuss an efficient way to minimize the time complexity.

Let's look at an example first,

    Array = [1, 2, 3, 4]
    Sub-arrays are
    [1] =1
    [2] =2
    [3] =3
    [4] =4
    [1, 2] =1+2=3
    [2, 3] =2+3= 5


    [3, 4] =3+4 =7
    [1, 2, 3] = 1+2+3= 6
    [2, 3, 4] = 2+3+4= 9
    [1, 2, 3, 4] = 1+2+3+4 = 10
    Total sum= 50

Let's concentrate on finding appearance on each element while calculating the total sum

If we notice carefully, we can find that we have calculated

Sum of

    4 1's = 4*1 = 4
    6 2's = 6*2 = 12
    6 3's = 6*3 = 18
    4 4's = 4*4 = 16
    Which is 50

So, if we can come up with an algorithm to find occurrences of each element for an n-length array, then we can compute the total sum in O(n). WE don't even need to compute subarray sums specifically & separately.

So, is there any such algorithm? There is.

A sub-array is a group of contagious elements

Now,

1. An element is a subarray can be the first element of the subarray.
2. It can be an intermediate or end element of a sub-array starting for any previous element in the array.

So, there is two option.

Now consider option 1.

Say an element is at index i of an n-length array

Then, how many sub-arrays are there which start from the particular element(arr[i])?

Answer is (n-i), of course

As the subarrays of these type are:

    [arr[i] ] //arr be the array name
    [arr[i], arr[i+1]]
    [arr[i], arr[i+1], arr[i+2] ]
    ...
    ...
    [arr[i], arr[i+1], arr[i+2], ..., arr[n-1]] // arr[n-1] is the last element
    So for option1 there is (n-i) occurences of the arr[i] already

Now consider option2,

There are i elements preceding the arr[i] (0-indexed, i-index element is actually (i+1)^th).

Now, arr[i] may be part of subarrays starting with any of this i (preceded) elements or may not be.

Like, for array
[1, 2, 3, 4]
Say i=2
arr[i]=3

arr[i] is part of sub-array [1,2,3] but not part of [1] or [1, 2] (both starting from 1 which is part of preceded elements).

Now the question is of how many subarrays of any preceded element, arr[i] is part of.

Answer is (n-i) as subarray containing arr[i](starting from any preced element) is similar to the number of subarray starting from arr[i].

Total number of occurrences for Option2 is then: i(n-i)

So, total occurrences of i-index element (arr[i]) =(n-i) + i*(n-i) =(i+1)*(n-i)

So, total sum can be calculated:

    for i=1: n
        sum+= arr[i]* (i+1) * (n-i)

Time complexity: O(n)

C++ implementation to find all subarray Sum of an array

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000007

long long int subarraysum(vector<int> arr, int n)
{
    long long int sum = 0;
    long long int pro;

    //calculation of the formula derived
    //arr[i]*(i+1)*(n-i)
    for (int i = 0; i < n; i++) {
        pro = ((arr[i] % MAX) * (i + 1) % MAX) % MAX;
        pro = ((pro % MAX) * ((n - i) % MAX)) % MAX;
        sum = ((sum % MAX) + (pro % MAX)) % MAX;
    }
    return sum;
}
int main()
{
    int n, item;

    cout << "enter array length\n";
    cin >> n;
    vector<int> arr;
    cout << "enter elements\n";
    for (int j = 0; j < n; j++) {
        cin >> item;
        arr.push_back(item);
    }

    cout << "Total subarray sum=> " << subarraysum(arr, n) << endl;

    return 0;
}

Output

enter array length
4
enter elements
1 2 3 4
Total subarray sum=> 50