Watch 10 video solutions for Sum of All Odd Length Subarrays, a easy level problem involving Array, Math, Prefix Sum. This walkthrough by Nate Santti has 36,564 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |