Problem

Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.

A subarray is a contiguous subsequence of the array.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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:

1
2
3

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

Example 3:

1
2

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

Solution

Method 1 - Naive

To solve this problem, we can use a direct approach of iterating through the array and summing all possible odd-length subarrays.

  1. For each possible starting index of the subarray, compute the sums of all odd-length subarrays starting from that index.
  2. Incrementally count subarrays with lengths 1, 3, 5, etc., while they are within the bounds of the array.

Code

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

public class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int totalSum = 0;

        for (int start = 0; start < n; start++) {
            for (int length = 1; start + length <= n; length += 2) {
                for (int j = start; j < start + length; j++) {
                    totalSum += arr[j];
                }
            }
        }

        return totalSum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def sumOddLengthSubarrays(arr):
    n = len(arr)
    total_sum = 0
    
    for start in range(n):
        subarray_sum = 0
        for length in range(1, n - start + 1, 2):
            subarray_sum += sum(arr[start:start + length])
            total_sum += subarray_sum
    
    return total_sum

Complexity

  • ⏰ Time complexity: O(n^3), where n is the length of the array. This is because we need to iterate through starting indices and subarray lengths.
  • 🧺 Space complexity: O(1), as we only use a constant amount of extra space.

Method 2 - Using kind of prefix sum

A more optimal solution involves counting the contribution of each element to the final sum, based on its position.

Here is the approach:

  • Calculate the contribution of each element to the sum of all odd-length subarrays:
    • For each element at index i, calculate how many subarrays of odd lengths include this element.
    • The contribution is given by the number of such subarrays multiplied by the element’s value.

Code

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

public class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int totalSum = 0;

        for (int i = 0; i < n; i++) {
            int start = i + 1;
            int end = n - i;
            int total = (start * end + 1) / 2;
            totalSum += total * arr[i];
        }

        return totalSum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def sumOddLengthSubarrays(arr):
    n = len(arr)
    total_sum = 0

    for i in range(n):
        start = i + 1
        end = n - i
        total = (start * end + 1) // 2
        total_sum += total * arr[i]

    return total_sum

Complexity

  • ⏰ Time complexity: O(n), This is because we are only iterating through the array once to calculate the contributions of each element.
  • 🧺 Space complexity: O(1), as it uses a constant amount of additional space.