Sum of All Odd Length Subarrays

Difficulty: Easy | Acceptance: 84.00% | Paid: No Topics: Array, Math, Prefix Sum

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.

Examples

Example 1:

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays are [1], [4], [2], [5], [3], [1,4,2], [4,2,5], [2,5,3], [1,4,2,5,3].
Their sum is 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58.

Example 2:

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]
Output: 66

Constraints

1 <= arr.length <= 100
1 <= arr[i] <= 1000

• Brute Force
• Prefix Sum
• Math

Brute Force

Intuition We can generate every possible subarray, check if its length is odd, and if so, sum its elements.

Steps

• Iterate through the array to define the starting index i of the subarray.
• Iterate through the array starting from i to define the ending index j.
• Calculate the length of the subarray as j - i + 1.
• If the length is odd, iterate from i to j to sum the elements and add to the total result.

class Solution:
    def sumOddLengthSubarrays(self, arr: list[int]) -> int:
        n = len(arr)
        total_sum = 0
        for i in range(n):
            for j in range(i, n):
                length = j - i + 1
                if length % 2 == 1:
                    for k in range(i, j + 1):
                        total_sum += arr[k]
        return total_sum

Complexity

• Time: O(n³) - Three nested loops are used.
• Space: O(1) - No extra space is used apart from variables.
• Notes: Simple to implement but inefficient for large arrays.

Prefix Sum

Intuition We can optimize the summation step by precomputing prefix sums. This allows us to calculate the sum of any subarray in O(1) time.

Steps

• Create a prefix sum array where prefix[i] is the sum of elements from arr[0] to arr[i-1]. Initialize prefix[0] = 0.
• Iterate through all possible start indices i and end indices j.
• If the subarray length j - i + 1 is odd, calculate the sum using prefix[j+1] - prefix[i] and add it to the total.

class Solution:
    def sumOddLengthSubarrays(self, arr: list[int]) -> int:
        n = len(arr)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + arr[i]
        
        total_sum = 0
        for i in range(n):
            for j in range(i, n):
                length = j - i + 1
                if length % 2 == 1:
                    total_sum += prefix[j + 1] - prefix[i]
        return total_sum

Complexity

• Time: O(n²) - Two nested loops to iterate over subarrays, with O(1) sum calculation.
• Space: O(n) - For storing the prefix sum array.
• Notes: Better time complexity than brute force, but uses extra space.

Math

Intuition Instead of finding subarrays, we can calculate the contribution of each element arr[i] to the final sum. An element arr[i] appears in (i + 1) * (n - i) subarrays in total (choices for start * choices for end). Exactly half of these (rounded up) will be of odd length.

Steps

• Iterate through each element arr[i] in the array.
• Calculate the total number of subarrays where arr[i] appears: total = (i + 1) * (n - i).
• Calculate the number of odd-length subarrays: odd_count = (total + 1) / 2 (using integer division).
• Add arr[i] * odd_count to the total sum.

class Solution:
    def sumOddLengthSubarrays(self, arr: list[int]) -> int:
        n = len(arr)
        total_sum = 0
        for i in range(n):
            total_subarrays = (i + 1) * (n - i)
            odd_subarrays = (total_subarrays + 1) // 2
            total_sum += arr[i] * odd_subarrays
        return total_sum

Complexity

• Time: O(n) - Single pass through the array.
• Space: O(1) - No extra space used.
• Notes: The most optimal solution for this problem.