Sum of All Odd Length Subarrays — Problem Statement & Solution Guide
Problem Description
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.
### Constraints:
* 1 <= arr.length <= 100
* 1 <= arr[i] <= 1000
### Follow-up:
Can you solve this problem in $\mathcal{O}(N)$ time complexity?
Examples
Input
[1, 4, 2, 5, 3]
Output
94
Explanation: Step-by-step: We calculate the sum of all odd-length subarrays of [1, 4, 2, 5, 3]. The odd-length subarrays are [1], [4], [2], [5], [3], [1, 4], [1, 2], [1, 5], [1, 3], [4, 2], [4, 5], [4, 3], [2, 5], [2, 3], [5, 3], [1, 4, 2], [1, 4, 5], [1, 2, 5], [1, 2, 3], [4, 2, 5], [4, 2, 3], [4, 5, 3], [2, 5, 3], [1, 4, 2, 5], [1, 4, 2, 3], [1, 4, 5, 3], [1, 2, 5, 3], [4, 2, 5, 3]. The sum of these subarrays is 1 + 4 + 2 + 5 + 3 + (1 + 4) + (1 + 2) + (1 + 5) + (1 + 3) + (4 + 2) + (4 + 5) + (4 + 3) + (2 + 5) + (2 + 3) + (5 + 3) + (1 + 4 + 2) + (1 + 4 + 5) + (1 + 2 + 5) + (1 + 2 + 3) + (4 + 2 + 5) + (4 + 2 + 3) + (4 + 5 + 3) + (2 + 5 + 3) + (1 + 4 + 2 + 5) + (1 + 4 + 2 + 3) + (1 + 4 + 5 + 3) + (1 + 2 + 5 + 3) + (4 + 2 + 5 + 3) = 94
Input
[1, 2, 3, 4, 5]
Output
28
Explanation: Step-by-step: We calculate the sum of all odd-length subarrays of [1, 2, 3, 4, 5]. The odd-length subarrays are [1], [2], [3], [4], [5], [1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5], [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]. The sum of these subarrays is 1 + 2 + 3 + 4 + 5 + (1 + 2) + (1 + 3) + (1 + 4) + (1 + 5) + (2 + 3) + (2 + 4) + (2 + 5) + (3 + 4) + (3 + 5) + (4 + 5) + (1 + 2 + 3) + (1 + 2 + 4) + (1 + 2 + 5) + (1 + 3 + 4) + (1 + 3 + 5) + (1 + 4 + 5) + (2 + 3 + 4) + (2 + 3 + 5) + (2 + 4 + 5) + (3 + 4 + 5) = 28
Constraints
- 1 <= arr.length <= 100
- 1 <= arr[i] <= 1000
Optimal Approach & Strategy
The optimal approach calculates the direct contribution of each element to the final sum in O(N) time. For each element arr[i], we count the total number of subarrays containing it, which is (i + 1) * (n - i). Since odd-length and even-length subarrays are distributed nearly equally, exactly ((i + 1) * (n - i) + 1) // 2 of these subarrays will have an odd length. We multiply each element by its odd-subarray frequency and sum them up.
Brute Force Approach
The brute-force approach generates all possible contiguous subarrays of odd lengths (1, 3, 5, etc.) using nested loops. For each odd-length subarray, we iterate through its elements to compute its sum and add it to the running total. This takes O(N³) time, which can be optimized to O(N²) using a running sum or prefix sums.
Verified Code Solutions
function sumOddLengthSubarrays(arr) {
let n = arr.length;
let prefixSum = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
let sum = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
if ((j - i + 1) % 2 !== 0) {
sum += prefixSum[j + 1] - prefixSum[i];
}
}
}
return sum;
}class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {
int n = arr.size();
vector<int> prefixSum(n + 1, 0);
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if ((j - i + 1) % 2 != 0) {
sum += prefixSum[j + 1] - prefixSum[i];
}
}
}
return sum;
}
};class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int n = arr.length;
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if ((j - i + 1) % 2 != 0) {
sum += prefixSum[j + 1] - prefixSum[i];
}
}
}
return sum;
}
}def sum_odd_length_subarrays(arr):
n = len(arr)
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + arr[i]
sum = 0
for i in range(n):
for j in range(i, n):
if (j - i + 1) % 2 != 0:
sum += prefix_sum[j + 1] - prefix_sum[i]
return sumfunction sumOddLengthSubarrays(arr) {
let n = arr.length;
let prefixSum = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
let sum = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
if ((j - i + 1) % 2 !== 0) {
sum += prefixSum[j + 1] - prefixSum[i];
}
}
}
return sum;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.