Sum of All Odd Length Subarrays Leetcode Solution

Table of Contents

Problem Statement

In this problem an array of positive integers is given. We have to calculate and return a single integer, the sum of all possible odd length subarrays of the given array. A subarray is a contiguous subsequence of the array.

Example

arr = [1,4,2,5,3]

Explanation:

The odd-length subarrays of arr and their sums are:
[1] = 1, [4] = 4, [2] = 2, [5] = 5, [3] = 3, [1,4,2] = 7, [4,2,5] = 11, [2,5,3] = 10, [1,4,2,5,3] = 15
Adding all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

arr = [1,2]

Explanation:

There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Approach (Brute Force)

To solve this problem by brute force, it is very easy to see from the problem that we just have to go for all odd length subarrays and calculate total sum and return it.
We can implement this by following simple steps:

1. Create a variable sum to store the total sum.
2. Run a for loop for all odd length subarrays starting from len=1 and keep incrementing the value by 2 while len <= n (size of the array).
3. Inside this loop, Run a loop for starting position of the subarray from i=0 to i= n-len.
4. Inside the above loop, run a loop for this subarray whose index starts from i and ends at i+len-1 and add all the elements of this subarray.
5. At last return the sum.

Implementation for Sum of All Odd Length Subarrays Leetcode Solution

C++ Program

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}

Java Program

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}

Complexity Analysis for Sum of All Odd Length Subarrays Leetcode Solution

Time Complexity

O(n^3) : We have used three loops in nested form where each loop is running following times:
First loop is running n/2 times.
Second loop is running (n-len) times, where len is 1,3,4,… .
Third loop is running len times.
Total time will be (n/2)*(n-len)*len. Hence upper bound of the time complexity will be O(n^3) Where n is the size of the given array.

Space Complexity

O(1) : Space complexity is constant.

Approach (Time Optimized)

As we can see that above brute force solution has O(n^3) time complexity. We can minimize this because in above approach we are adding the same element multiple times for different subarrays. If somehow we know how many times a particular element is added or should be added to the total sum, then we can reduce the time complexity from O(n^3) to O(n).

We can analyse that if we take all subarrays (even and odd length), then in that case a particular element at index i will occur in all subarrays whose starting index is less than equal to i, and ending index is greater than equal to i.

Therefore we can say that total number of those subarrays which contains arr[i] (0-indexed) will be equal to (i+1)*(n-i).
Let this value to be x.
Out of which there are (x+1)/2 odd length subarrays which contains arr[i].
And x/2 even length subarrays which contains arr[i].
Hence a[i] will contribute (x+1)/2 times in the total sum in our solution.

We can see this with a simple example:

Let arr = [1, 2, 3, 4, 5]

Hence contribution of each element arr[i] in odd subarrays = arr[i]* ((i+1)*(n-i) +1)/2.
This can be done using a single loop and hence time complexity of this solution will be linear.