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 <= 1001 <= arr[i] <= 1000
Follow up:
Could you solve this problem in O(n) time complexity?
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.
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.
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.
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.
Time Complexity: O(n), much improved by calculating contributions directly.
Space Complexity: O(1), only a few extra integer variables.
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).
| Approach | Complexity |
|---|---|
| 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) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n^3) | O(1) | Useful for understanding how subarrays are generated and validating the odd-length constraint |
| Mathematical Contribution Counting | O(n) | O(1) | Best general solution; counts how many odd-length subarrays include each element |
Sum of All Odd Length Subarrays | LeetCode 1588 | Explained and Java Code • Nate Santti • 36,564 views views
Watch 9 more video solutions →Practice Sum of All Odd Length Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor