Algorithms to Sum of All Odd Length Subarrays

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays. A subarray is a contiguous subsequence of the array. Return the sum of all odd-length subarrays of arr.

Example 1:
Input: arr = [1,4,2,5,3]
Output: 58

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
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:
Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:
Input: arr = [10,11,12]
Output: 66

Constraints:
1 <= arr.length <= 100
1 <= arr[i] <= 1000

Hint: You can brute force – try every (i,j) pair, and if the length is odd, go through and add the sum to the answer.

Bruteforce Algorithm to Compute the Sum of All Odd Length Subarrays

Since the given input array size of maximum 100, we can bruteforce. We can bruteforce every pair of (i, j) and compute the sum of subarray from index i to j – when the sub array are length of odd numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {    
        int sum = 0;
        for (int i = 0; i < arr.size(); ++ i) {
            for (int j = i; j < arr.size(); ++ j) {
                if (((j - i + 1) & 1) == 0) {
                    continue;
                }
                for (int k = i; k <= j; ++ k) {
                    sum += arr[k];
                }
            }
        }
        return sum;
    }
};

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {    
        int sum = 0;
        for (int i = 0; i < arr.size(); ++ i) {
            for (int j = i; j < arr.size(); ++ j) {
                if (((j - i + 1) & 1) == 0) {
                    continue;
                }
                for (int k = i; k <= j; ++ k) {
                    sum += arr[k];
                }
            }
        }
        return sum;
    }
};

The time complexity is O(N^3) as we are using another inner loop to compute the sum. This can be improved by using an accumulated sum, thus improving the solution to O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {        
        int ans = 0;
        for (int i = 0; i < arr.size(); ++ i) {
            int sum = 0;
            for (int j = i; j < arr.size(); ++ j) {
                sum += arr[j];
                if (((j - i + 1) & 1) == 0) {
                    continue;
                }
                ans += sum;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {        
        int ans = 0;
        for (int i = 0; i < arr.size(); ++ i) {
            int sum = 0;
            for (int j = i; j < arr.size(); ++ j) {
                sum += arr[j];
                if (((j - i + 1) & 1) == 0) {
                    continue;
                }
                ans += sum;
            }
        }
        return ans;
    }
};

O(N) linear algorithm to compute the sum of subarray of odd length

We can sum up the contribution of A[i] – then it will be a linear solution.

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) { 
        int res = 0, n = A.size();
        for (int i = 0; i < n; ++i) {
            res += ((i + 1) * (n - i) + 1) / 2 * A[i];
        }
        return res;
    }
}

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) { 
        int res = 0, n = A.size();
        for (int i = 0; i < n; ++i) {
            res += ((i + 1) * (n - i) + 1) / 2 * A[i];
        }
        return res;
    }
}

–EOF (The Ultimate Computing & Technology Blog) —