Sum of All Odd Length Subarrays
Problem
Given a positive integer array arr, return the sum of all possible odd-length subarrays.
arr = [1,4,2,5,3]58def sum_odd_length_subarrays(arr):
n = len(arr); total = 0
for i, v in enumerate(arr):
left, right = i + 1, n - i
full = left * right
odd = (full + 1) // 2
total += v * odd
return totalfunction sumOddLengthSubarrays(arr) {
const n = arr.length; let total = 0;
for (let i = 0; i < n; i++) {
const left = i + 1, right = n - i;
const full = left * right, odd = (full + 1) >> 1;
total += arr[i] * odd;
}
return total;
}class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int n = arr.length, total = 0;
for (int i = 0; i < n; i++) {
int left = i + 1, right = n - i;
int full = left * right, odd = (full + 1) / 2;
total += arr[i] * odd;
}
return total;
}
}int sumOddLengthSubarrays(vector& arr) {
int n = arr.size(), total = 0;
for (int i = 0; i < n; i++) {
int left = i + 1, right = n - i;
int full = left * right, odd = (full + 1) / 2;
total += arr[i] * odd;
}
return total;
} Explanation
Rather than listing every odd-length subarray and adding them up, we ask a smarter question for each element: how many odd-length subarrays contain it? Multiply that count by the value and sum across all elements.
A subarray that includes index i picks a start at or before i and an end at or after i. There are left = i + 1 choices for the start and right = n - i choices for the end, so full = left * right subarrays cover i in total.
Exactly half of those have odd length (rounding up), which is odd = (full + 1) // 2. So index i contributes arr[i] * odd to the answer, and we just accumulate that.
Example: arr = [1,4,2,5,3], n = 5. For the middle index i=2: left=3, right=3, full=9, odd=5, so it adds 2*5 = 10. Doing this for every index totals 58.
It is a single pass with O(1) math per element, so O(n) time and O(1) extra space.