Skip to main content
Talentd

Sum of All Odd Length Subarrays - Solution & Explanation

EasyArrayMathPrefix Sum15 min readAsked at: Amazon, Google, LinkedIn
Practice this problem

Problem Statement

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.

 

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

 

Follow up:

Could you solve this problem in O(n) time complexity?

Approach Overview

Problem Overview: You are given an integer array and must compute the total sum of every subarray whose length is odd. Each valid subarray contributes the sum of its elements to the final result, so the task is to efficiently enumerate or calculate these contributions without redundant work.

Approach 1: Brute Force Enumeration (Time: O(n^3), Space: O(1))

The most direct solution iterates over every possible subarray and checks whether its length is odd. Use two nested loops to choose the start and end indices, then compute the subarray sum with a third loop. If (end - start + 1) is odd, add the sum to the result. This approach clearly demonstrates the problem mechanics: generate subarrays, validate length, accumulate values. However, repeated summation of overlapping ranges causes heavy redundancy, making it inefficient for larger inputs.

Approach 2: Mathematical Contribution Counting (Time: O(n), Space: O(1))

The optimal insight comes from counting how many odd-length subarrays include each element. For an index i, there are (i + 1) ways to choose a starting position to the left and (n - i) ways to choose an ending position to the right. Multiplying these gives the total number of subarrays containing that element. Only half of those will have odd length. The exact count is ((i + 1) * (n - i) + 1) // 2. Multiply this frequency by arr[i] and accumulate the result. This converts the problem from enumerating subarrays to counting element contributions.

This approach is essentially a counting trick built on properties of array indices and parity. Instead of explicitly forming subarrays, you compute how often each value appears in valid odd-length windows. The algorithm performs a single pass through the array and requires constant extra memory.

Although the problem can also be reasoned about using cumulative sums similar to prefix sum techniques, the contribution formula derived from simple math reasoning gives the cleanest O(n) implementation.

Recommended for interviews: The mathematical contribution approach is what interviewers typically expect. Starting with the brute force method shows you understand subarray generation and the constraint on odd lengths. Deriving the contribution formula demonstrates deeper algorithmic thinking and reduces the complexity from O(n^3) to O(n) with constant space.

Approach 1: Brute Force Approach

The brute force approach involves iterating over every possible subarray, checking if its length is odd, and then summing its elements. This approach is straightforward but not optimal.

This C program utilizes nested loops to generate subarrays. The outer two loops iterate through all start and end indices. The innermost loop sums the elements of the current subarray if its length is odd.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) where n is the number of elements in the array, due to triple nested loops.

Space Complexity: O(1), only a few extra variables are utilized.

Try this approach in the editor →

Approach 2: Optimized Mathematical Approach

The optimized approach calculates the contribution of each element to the final sum using a mathematical formula. For each element at index i, calculate how many odd-length subarrays it can contribute to, then sum directly based on these contributions.

This solution computes the contribution of each element to possible odd-length subarrays using a mathematical formula. For each element, calculate how many subarrays include the element, split this into odd/even counts, and then use that to determine its overall contribution to the sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), much improved by calculating contributions directly.

Space Complexity: O(1), only a few extra integer variables.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^3) where n is the number of elements in the array, due to triple nested loops.

Space Complexity: O(1), only a few extra variables are utilized.

Optimized Mathematical Approach

Time Complexity: O(n), much improved by calculating contributions directly.

Space Complexity: O(1), only a few extra integer variables.

Dynamic Programming (Space Optimization)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n^3)O(1)Useful for understanding how subarrays are generated and validating the odd-length constraint
Mathematical Contribution CountingO(n)O(1)Best general solution; counts how many odd-length subarrays include each element

Video Solution

Sum of All Odd Length Subarrays | LeetCode 1588 | Explained and Java Code • Nate Santti • 37,021 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of All Odd Length Subarrays easy or hard?
Sum of All Odd Length Subarrays is rated Easy on LeetCode with a high acceptance rate. The brute-force idea is straightforward, but recognizing the O(n) mathematical contribution approach demonstrates stronger algorithmic insight.
How to solve Sum of All Odd Length Subarrays in O(n)?
Iterate through the array and compute how many odd-length subarrays contain each element. For position i, compute total subarrays including that element as (i + 1) * (n - i). Half of those, rounded up, have odd length. Multiply that count by arr[i] and add it to the answer while scanning the array once.
Sum of All Odd Length Subarrays Python or Java solution?
Python and Java implementations follow the same idea: loop through the array, compute ((i + 1) * (n - i) + 1) // 2 to determine how many odd-length subarrays include arr[i], then accumulate arr[i] multiplied by that count. The logic is identical across Python, Java, C++, and other languages.
What is the best approach for Sum of All Odd Length Subarrays?
The best approach uses a mathematical contribution formula that counts how many odd-length subarrays include each element. For index i, there are (i + 1) possible starts and (n - i) possible ends, and roughly half of these combinations produce odd lengths. The element contributes arr[i] * (((i + 1) * (n - i) + 1) // 2) to the final sum. This yields an O(n) time and O(1) space solution.
What data structure is used in Sum of All Odd Length Subarrays?
The problem primarily uses arrays and basic arithmetic reasoning. The optimal solution relies on mathematical counting of index combinations rather than additional data structures, though the concept relates to prefix-sum style reasoning about subarray ranges.
What is the time complexity of Sum of All Odd Length Subarrays?
The optimal solution runs in O(n) time with O(1) extra space because each element's contribution is computed in constant time during a single pass through the array. A naive brute force solution that enumerates and sums every odd-length subarray takes O(n^3) time.
Is Sum of All Odd Length Subarrays asked at Google, Amazon, or Meta?
Sum of All Odd Length Subarrays is categorized as an Easy array and math problem but still appears in interview preparation sets for companies like Amazon and Google. It tests whether candidates recognize contribution counting patterns instead of brute-force enumeration.

Ready to solve this problem?

Practice Sum of All Odd Length Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sum of Squares of Special Elements