Sum of All Odd Length Subarrays
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
arr = [1,4,2,5,3]58The 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
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). Half of these (rounded up) have odd length. Multiplying the element's value by this count and summing over all elements yields the total sum in O(n) time.
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.
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
| 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 |
Step-by-Step Solution
Calculate Array Length and Initialize Accumulator
| 3 | n = len(arr) |
| 4 | ans = 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
| 5 | for i in range(n): |
| 6 | total = (i + 1) * (n - i) |
| 7 | odd = (total + 1) // 2 |
| 8 | ans += arr[i] * odd |
Objective
To compute and add each element's contribution based on the count of odd-length subarrays it belongs to.
Key Insight
Each element's contribution is its value multiplied by the count of odd-length subarrays containing it. The total subarrays containing element i is (i + 1) * (n - i). Half of these (rounded up) are odd-length. This formula efficiently captures the element's total impact on the final sum without enumerating subarrays.
Interview Quick-Check
Core Logic
Calculate total subarrays containing element i as (i + 1) * (n - i), then compute odd-length subarrays as (total + 1) // 2 to count only odd-length ones.
Common Pitfalls & Bugs
Forgetting to add 1 before integer division can lead to incorrect counts of odd-length subarrays.
Complexity
This approach reduces the problem from O(n^2) enumeration to O(n) arithmetic operations.
Return the Accumulated Sum of Odd-Length Subarrays
| 9 | return ans |
Objective
To output the final computed sum after processing all elements.
Key Insight
Returning the accumulator completes the algorithm, providing the sum of all odd-length subarrays without explicit enumeration.
Interview Quick-Check
Core Logic
Returning ans delivers the final result computed by summing weighted contributions of all elements.
Line Analysis
This solution has 1 Critical line interviewers watch for.
odd = (total + 1) // 2Compute 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.
total = (i + 1) * (n - i)Calculate the total number of subarrays containing the current element.
The formula (i + 1) * (n - i) counts all subarrays that include element i by considering all possible start and end indices that cover i.
ans += arr[i] * oddAdd the weighted contribution of the current element to the accumulator.
Multiplying the element's value by the count of odd-length subarrays it belongs to and adding to ans aggregates the total sum without enumerating subarrays.
return ansReturn the accumulated sum of all odd-length subarrays.
Returning ans provides the final answer, completing the algorithm by outputting the sum computed through combinatorial counting.
n = len(arr)Calculate the length of the input array.
Knowing the array length is fundamental to determining how many subarrays include each element, enabling the combinatorial counting approach.
for i in range(n):Begin iterating over each element's index in the array.
Processing each element individually allows calculation of its contribution based on its position and the array length.
ans = 0Initialize the accumulator for the final sum.
Starting with zero ensures a clean state for accumulating the weighted contributions of each element.
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?
Because each element's total contribution to the sum is its value multiplied by the number of odd-length subarrays it appears in. Summing these weighted contributions over all elements accounts for every odd-length subarray exactly once, eliminating the need for explicit enumeration.
Related Problems
Math pattern
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