Sum of All Odd Length Subarrays — Problem Statement & Solution Guide

ArraysEasy

TimeO(N)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Sum of All Odd Length Subarrays problem optimally.

TopicArrays

PatternOptimal Strategy

TimeO(N)

SpaceO(1)

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?

DSA Pattern Breakdown

"Sum of All Odd Length Subarrays"

easy

WHY DOES IT MATTER?

Understanding element contribution transforms a seemingly quadratic problem into a linear one.

OPTIMIZATION CHALLENGE

The key is to replace explicit enumeration with a closed‑form count of appearances.

REAL-WORLD CONNECTION

It mirrors cache‑hit analysis where each request’s impact is counted across overlapping time windows.

Pre‑compute left/right lengths once and reuse them; avoid any nested loops for subarray generation.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(1)

Core Theory — Why This Approach?

The straightforward solution enumerates every possible subarray, checks its length, and accumulates its sum. This double‑loop approach runs in O(N^2) time and, with an inner loop to compute each subarray’s sum, can degrade to O(N^3) for large N, quickly exceeding limits even for modest input sizes.\n\nThe optimal O(N) method leverages combinatorial contribution: each element arr[i] participates in (i+1)*(n-i) subarrays, half of which have odd length (rounded up). By multiplying the element’s value by the count of odd‑length subarrays it belongs to and summing across all indices, we obtain the answer in linear time with O(1) extra space.

Interview Questions on This Problem

Q1How can you compute the number of odd‑length subarrays that include a given element at index i?

Calculate left = i + 1 and right = n - i. The odd count is ((left * right) + 1) // 2, which is the number of subarrays of odd length that contain arr[i].

Q2Why does the naive O(N^2) enumeration become O(N^3) when summing each subarray?

Each subarray sum is recomputed by iterating over its elements, adding another linear factor. Thus, for N subarrays of average length N/2, the total work grows cubicly.

Q3Can this problem be solved with prefix sums in O(N) time?

Prefix sums alone still require iterating over all subarray lengths, so they don’t remove the quadratic factor. The contribution formula is the only linear‑time path.

Examples

Example 1

Input

[1, 4, 2, 5, 3]

Output

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

Example 2

Input

[1, 2, 3, 4, 5]

Output

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

For each index i, compute left = i+1, right = n-i, oddCount = ((left*right)+1)//2, and add arr[i]*oddCount to the result.

Brute Force Approach

Loop over every possible start and end index, check if (end‑start+1) is odd, and add the subarray sum.

Code Solutions

Language:

JavaScript Solution

Time: O(N)

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 sum

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;
}

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.