Problem statement

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

A subarray is a contiguous slice of the array.

Example 1

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays are [1],[4],[2],[5],[3],[1,4,2],[4,2,5],[2,5,3],[1,4,2,5,3], summing to 58.

Example 2

Input: arr = [1,2]
Output: 3
Explanation: Only [1] and [2] have odd length.

Example 3

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

Constraints

• 1 <= arr.length <= 30
• 1 <= arr[i] <= 1000

Follow-up: The O(n³) enumeration is easy. Can you do it in O(n)?

Hints for Sum of All Odd Length Subarrays

1. Hint 1

   Instead of enumerating subarrays, ask how many odd-length subarrays contain each element.

2. Hint 2

   Element i has i + 1 choices of left endpoint and n - i choices of right endpoint, so it sits in (i + 1) × (n - i) subarrays in total.

3. Hint 3

   Exactly half of those have odd length, rounded up: ((i + 1) × (n - i) + 1) / 2.

How to solve Sum of All Odd Length Subarrays

Count how many odd-length subarrays contain each element, then multiply. Element i sits in (i + 1)·(n - i) subarrays, and just over half of those have odd length.

Approach

1. For each i, compute occurrences = ((i + 1)·(n - i) + 1) // 2.
2. Add occurrences × arr[i] to the total.

Why it works

A subarray containing i is fixed by a left endpoint in [0, i] and a right endpoint in [i, n-1]. Pairing lengths L and L + 1 shows odd and even lengths alternate, so odd ones number ⌈total/2⌉.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Enumerating every subarray is O(n²) (fine here) or O(n³) if you re-sum each — the contribution formula is what the problem is testing.

Reference solution

Python

def sumOddLengthSubarrays(arr):
    n = len(arr)
    total = 0
    for i, x in enumerate(arr):
        occurrences = ((i + 1) * (n - i) + 1) // 2
        total += occurrences * x
    return total

Java

public static int sumOddLengthSubarrays(int[] arr) {
    int n = arr.length;
    int total = 0;
    for (int i = 0; i < n; i++) {
        int occurrences = ((i + 1) * (n - i) + 1) / 2;
        total += occurrences * arr[i];
    }
    return total;
}

C++

int sumOddLengthSubarrays(vector<int>& arr) {
    int n = (int) arr.size();
    int total = 0;
    for (int i = 0; i < n; i++) {
        int occurrences = ((i + 1) * (n - i) + 1) / 2;
        total += occurrences * arr[i];
    }
    return total;
}

JavaScript

var sumOddLengthSubarrays = function(arr) {
    const n = arr.length;
    let total = 0;
    for (let i = 0; i < n; i++) {
        const occurrences = Math.floor(((i + 1) * (n - i) + 1) / 2);
        total += occurrences * arr[i];
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy