Sum of All Odd Length Subarrays

Q: What is the time complexity of Sum of All Odd Length Subarrays?

O(n). The solution iterates through the array once, performing constant-time calculations per element, resulting in linear time complexity.

Q: What pattern does Sum of All Odd Length Subarrays use?

The Pattern: Math & Geometry (Combinatorial Counting) The Heuristic: When asked to sum over all subarrays with a length constraint, avoid explicit enumeration by counting how many subarrays each element participates in and weighting its contribution accordingly.

Easy Math & Geometry

Problem

Given an integer array arr, return the sum of all possible odd-length subarrays of arr.

1 ≤ arr.length ≤ 100
1 ≤ arr[i] ≤ 1000

Example

Input: arr = [1,4,2,5,3]

Output: 58

The brute-force approach would enumerate all odd-length subarrays: [1], [4], [2], [5], [3], [1,4,2], [4,2,5], [2,5,3], [1,4,2,5,3], and sum them to get 58. Instead of enumerating subarrays, the algorithm counts how many odd-length subarrays each element belongs to and multiplies that count by its value. For example, the element 4 at index 1 is contained in 4 odd-length subarrays, contributing 4 × 4 = 16. Summing all element contributions yields 58.

Approach

Straightforward Solution

A brute-force approach enumerates all odd-length subarrays, sums their elements, and accumulates the total. This approach is O(n^2) or worse, which is inefficient for larger arrays.

Core Observation

Each element contributes to multiple subarrays. The total number of subarrays containing element at index i is (i + 1) * (n - i). Among these, half (rounded up) are odd-length subarrays. This counting avoids enumerating all subarrays explicitly.

Path to Optimal

Preview

The key insight is to count the number of odd-length subarrays each element belongs to without enumerating them. For element i, total subarrays containing it is (i + 1) * (n - i)…

Full step-by-step walkthrough on Pro →

Optimal Approach

Iterate through each element, compute total subarrays containing it as (i + 1) * (n - i), calculate odd-length subarrays as (total + 1) // 2, then add arr[i] * odd to the answer. Return the accumulated sum after processing all elements.

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The solution iterates through the array once, performing constant-time calculations per element, resulting in linear time complexity.

Space

O(1)

Only a few variables are used for counting and accumulation, so the auxiliary space is constant regardless of input size.

Pattern Spotlight

Math & Geometry (Combinatorial Counting)

When asked to sum over all subarrays with a length constraint, avoid explicit enumeration by counting how many subarrays each element participates in and weighting its contribution accordingly.

Solution

Python

1class Solution:
  def sumOddLengthSubarrays(self, arr):
      n = len(arr)
      ans = 0
      for i in range(n):
          total = (i + 1) * (n - i)
          odd = (total + 1) // 2
          ans += arr[i] * odd
      return ans

Step-by-Step Solution

Calculate Array Length and Initialize Accumulator

3n = len(arr)
4ans = 0

Objective

To determine the size of the input array and prepare a variable to accumulate the final sum.

Key Insight

Knowing the array length is essential for calculating how many subarrays include each element. Initializing the accumulator to zero sets up a clean state for summing contributions.

Interview Quick-Check

Core Logic

The length n is used to compute the total number of subarrays containing each element.

State & Boundaries

Initializing ans to zero ensures correct accumulation without residual values.

Iterate Over Elements to Accumulate Weighted Contributions

To compute and add each element's contribution based on the count of odd-length subarrays it belongs to.

Return the Accumulated Sum of Odd-Length Subarrays

To output the final computed sum after processing all elements.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 7 Critical

odd = (total + 1) // 2

Compute the number of odd-length subarrays containing the current element.

This line implements the key combinatorial insight: half of the subarrays containing an element are odd-length, and adding 1 before division ensures correct rounding, which is essential for precise counting.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why does counting the number of odd-length subarrays each element belongs to allow us to compute the total sum without enumerating all subarrays?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Sum of All Odd Length Subarrays from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sum of All Odd Length Subarrays drill

or drill a free problem

1	`class Solution:`
2	`def sumOddLengthSubarrays(self, arr):`
3	`n = len(arr)`
4	`ans = 0`
5	`for i in range(n):`
6	`total = (i + 1) * (n - i)`
7	`odd = (total + 1) // 2`
8	`ans += arr[i] * odd`
9	`return ans`