#1588

Easy

LeetCode Problem Workspace

Sum of All Odd Length Subarrays

Calculate the sum of all odd-length subarrays in a given integer array using efficient array and math strategies.

Problem Statement

Given an array of positive integers arr, return the sum of all possible subarrays that have an odd length. A subarray is defined as a contiguous sequence of elements in arr. Consider how each element appears in multiple odd-length subarrays and affects the total sum.

For example, if arr = [1,4,2,5,3], all odd-length subarrays include [1], [4], [2], [5], [3], [1,4,2], [4,2,5], [2,5,3], and [1,4,2,5,3]. The sum of all these subarrays is 58. Constraints are 1 <= arr.length <= 100 and 1 <= arr[i] <= 1000.

Examples

Example 1

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

Output: 58

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

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

Example 3

Input: arr = [10,11,12]

Output: 66

Example details omitted.

Constraints

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

Solution Approach

Brute Force Approach

Loop through all possible subarray start and end indices, check if the length is odd, and sum the elements. This approach is straightforward and demonstrates the pattern of how elements contribute to multiple subarrays, but it is less efficient for larger arrays.

Prefix Sum Optimization

Compute the prefix sum array first, then use it to calculate subarray sums in O(1) per subarray. Iterate through all start and end indices of odd lengths, and subtract prefix sums to quickly get each subarray sum. This reduces repeated summation overhead and ties directly to the Array plus Math pattern.

Contribution Counting Formula

For each element arr[i], determine how many odd-length subarrays include it. Multiply arr[i] by this count and sum across all elements. This approach avoids nested loops entirely, applying math to count contributions efficiently and illustrates the exact failure mode avoided by brute force.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Brute force has O(n^3) time due to nested loops for all subarrays, while prefix sum reduces subarray sum computation to O(1), leading to O(n^2) overall. Contribution counting reduces time further to O(n) with constant space, maintaining O(1) extra memory.

What Interviewers Usually Probe

Checks if you can identify the relationship between element positions and odd-length subarrays.
Wants a solution that avoids summing each subarray explicitly for larger arrays.
Tests your ability to apply prefix sums or direct counting formulas in array problems.

Common Pitfalls or Variants

Common pitfalls

Forgetting that only odd-length subarrays count and summing even-length subarrays by mistake.
Attempting brute force without optimization, leading to unnecessary O(n^3) time.
Miscalculating the contribution count for each element in the formula approach.

Follow-up variants

Compute the sum of all even-length subarrays instead of odd-length ones.
Find the average of all odd-length subarrays rather than the sum.
Return a list of sums for each odd-length subarray instead of the total sum.

FAQ

What is the easiest way to sum all odd-length subarrays?

Use the contribution counting formula to calculate how many odd-length subarrays each element appears in, then multiply by the element value and sum.

Can prefix sums improve performance for this problem?

Yes, prefix sums allow O(1) computation of any subarray sum, reducing nested summation in brute force approaches.

Does this problem work with negative numbers?

The original constraints specify positive integers, but the contribution and prefix sum approaches can extend to negatives without structural changes.

Why is counting contributions better than brute force?

Counting avoids iterating over all subarrays and leverages mathematical patterns, giving O(n) time instead of O(n^3).

How does this problem relate to the Array plus Math pattern?

It combines array traversal with combinatorial counting and prefix sum calculations, exemplifying the Array plus Math pattern.

terminal

Solution

Solution 1: Dynamic Programming

We define two arrays $f$ and $g$ of length $n$, where $f[i]$ represents the sum of subarrays ending at $\textit{arr}[i]$ with odd lengths, and $g[i]$ represents the sum of subarrays ending at $\textit{arr}[i]$ with even lengths. Initially, $f[0] = \textit{arr}[0]$, and $g[0] = 0$. The answer is $\sum_{i=0}^{n-1} f[i]$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        f = [0] * n
        g = [0] * n
        ans = f[0] = arr[0]
        for i in range(1, n):
            f[i] = g[i - 1] + arr[i] * (i // 2 + 1)
            g[i] = f[i - 1] + arr[i] * ((i + 1) // 2)
            ans += f[i]
        return ans

Solution 2: Dynamic Programming (Space Optimization)

We notice that the values of $f[i]$ and $g[i]$ only depend on $f[i - 1]$ and $g[i - 1]$. Therefore, we can use two variables $f$ and $g$ to record the values of $f[i - 1]$ and $g[i - 1]$, respectively, thus optimizing the space complexity.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        f = [0] * n
        g = [0] * n
        ans = f[0] = arr[0]
        for i in range(1, n):
            f[i] = g[i - 1] + arr[i] * (i // 2 + 1)
            g[i] = f[i - 1] + arr[i] * ((i + 1) // 2)
            ans += f[i]
        return ans

Continue Practicing

#1524 number of sub arrays with odd sum #1685 sum of absolute differences in a sorted array #1442 count triplets that can form two arrays of equal xor