Sum of All Odd Length Subarrays: Count Each Element's Contribution

You are given an array of positive integers, and you need to return the sum of every subarray that has an odd length. If you enumerate all those subarrays and add them up, you get the right answer, but there is a much faster way that requires just one pass through the array.

This is LeetCode 1588: Sum of All Odd Length Subarrays, an easy problem that teaches you how to think about contribution counting, a technique that shows up in many array and math problems.

For example, given arr = [1, 4, 2, 5, 3], the odd-length subarrays are [1], [4], [2], [5], [3], [1,4,2], [4,2,5], [2,5,3], and [1,4,2,5,3]. Their sums add up to 58.

The problem

Given an array arr of positive integers, return the sum of all possible odd-length subarrays. A subarray is a contiguous portion of the array. You want every subarray whose length is 1, 3, 5, and so on.

The brute force approach

The most direct way is to iterate over every possible starting index and every possible odd length, then sum the elements of each subarray. For each starting index i, you try lengths 1, 3, 5, etc., as long as the subarray fits within the array. You accumulate each subarray's sum into a running total.

This works fine for small arrays, but it runs in O(n^3) time because you have O(n^2) subarrays and each one takes O(n) to sum. You can improve it to O(n^2) by using prefix sums to compute each subarray sum in O(1), but you can do even better.

The key insight

Instead of summing subarrays one by one, flip the question: for each element arr[i], how many odd-length subarrays include it? If you can answer that, the total is just the sum of arr[i] * count[i] for each index.

For an element at index i in an array of length n, the number of subarrays that contain it equals (i + 1) * (n - i). That is the total number of subarrays (both odd and even length) that pass through index i. Among those, roughly half have odd length and half have even length. Specifically, the number of odd-length subarrays containing arr[i] is ceil((i + 1) * (n - i) / 2).

Step-by-step walkthrough

The code

def sumOddLengthSubarrays(arr):
    n = len(arr)
    total = 0
    for i in range(n):
        subarrays = (i + 1) * (n - i)
        odd_count = (subarrays + 1) // 2
        total += arr[i] * odd_count
    return total

The function walks through each index once. At each position, it computes the total number of subarrays that include arr[i] using the formula (i + 1) * (n - i). The factor (i + 1) counts how many choices you have for the left endpoint (indices 0 through i), and (n - i) counts how many choices you have for the right endpoint (indices i through n - 1).

To get only the odd-length count, you take the ceiling of half: (subarrays + 1) // 2. Then you multiply by arr[i] to get that element's total contribution, and accumulate into total.

Complexity analysis

The brute force visits every subarray and sums it element by element. The prefix sum approach precomputes cumulative sums so each subarray sum is O(1), but you still enumerate O(n^2) subarrays. The contribution counting approach makes a single pass, computing each element's participation count with a constant-time formula, giving O(n) total time and O(1) extra space.

The building blocks

Contribution counting

Instead of iterating over all subarrays, you figure out how many subarrays each element belongs to. This transforms a nested-loop problem into a single-pass problem. You will see this same idea in problems like "sum of subarray minimums" and "sum of subarray ranges," where the contribution of each element depends on its position relative to its neighbors.

Combinatorial subarray counting

The formula (i + 1) * (n - i) counts subarrays through index i by multiplying the number of valid left endpoints by the number of valid right endpoints. This is a counting principle you will use any time you need to enumerate subarrays that pass through a given index.

Edge cases

• Single element arr = [7]: there is exactly one subarray of length 1. The answer is 7.

• Two elements arr = [1, 2]: the odd-length subarrays are [1] and [2]. The answer is 3. There are no length-3 subarrays because the array is too short.

• All identical values arr = [3, 3, 3, 3]: every odd-length subarray sums to a multiple of 3. The formula still works because it counts appearances, not values.

• Maximum size: with n up to 100 and values up to 1000, the maximum possible answer fits well within standard integer bounds.

From understanding to recall

You have seen that the key move is flipping from "iterate over subarrays" to "iterate over elements and count their appearances." This is a powerful technique, but it is easy to forget the exact formula under pressure.

The formula (i + 1) * (n - i) for total subarrays through an index, and the ceiling-half trick for odd-length filtering, are worth drilling until they are automatic. If you can recall these two pieces instantly, you solve the problem in seconds.

Spaced repetition is the most reliable way to lock in formulas like this. You write the solution from scratch today, again in a few days, and once more next week. After a few rounds, the contribution counting pattern and the subarray counting formula become second nature. When a harder problem requires the same building block, you will not need to re-derive it.

Related posts

• Running Sum of 1d Array - A gentler introduction to prefix sums, the accumulation pattern this problem builds on
• Subarray Sum Equals K - Uses prefix sums with a hash map to count subarrays with a target sum
• Subarray Sums Divisible by K - Another prefix sum and counting problem involving subarray properties