Problem Description

Given an array of positive integers arr, you need to find the sum of all possible odd-length subarrays.

A subarray is a contiguous sequence of elements from the array. For example, if arr = [1, 2, 3], the subarrays are:

• Length 1 (odd): [1], [2], [3]
• Length 2 (even): [1, 2], [2, 3]
• Length 3 (odd): [1, 2, 3]

The odd-length subarrays are [1], [2], [3], and [1, 2, 3]. The sum would be 1 + 2 + 3 + (1 + 2 + 3) = 12.

The task is to calculate the sum of all elements in all odd-length subarrays and return this total sum.

Intuition

When we look at subarrays ending at each position, we can notice a pattern in how odd and even length subarrays are formed. For any position i, we need to track two things: the sum of odd-length subarrays ending at i and the sum of even-length subarrays ending at i.

The key insight is that when we extend a subarray by one element, its length parity (odd/even) flips. If we have an even-length subarray and add one more element, it becomes odd. Similarly, an odd-length subarray becomes even when extended.

Consider position i. When we include arr[i]:

• All even-length subarrays ending at i-1 become odd-length when extended to include arr[i]
• All odd-length subarrays ending at i-1 become even-length when extended to include arr[i]
• Additionally, arr[i] itself forms a new odd-length subarray of length 1

This alternating relationship suggests we can use dynamic programming with two states. If we know the sum of odd-length subarrays ending at position i-1 and the sum of even-length subarrays ending at position i-1, we can compute the corresponding values for position i.

The contribution of arr[i] to these sums depends on how many subarrays of each type it participates in. By analyzing the pattern of how subarrays are formed at each position, we can determine that the count follows a specific formula based on the index i. This leads to the mathematical expressions (i // 2) + 1 for odd-length subarrays and ((i + 1) // 2) for even-length subarrays.

Learn more about Math and Prefix Sum patterns.

Solution Approach

We implement a dynamic programming solution using two arrays f and g, where:

• f[i] represents the sum of all odd-length subarrays ending at position i
• g[i] represents the sum of all even-length subarrays ending at position i

Initialization:

• f[0] = arr[0] because the only subarray ending at position 0 is [arr[0]] itself, which has odd length 1
• g[0] = 0 because there are no even-length subarrays ending at position 0

State Transition:

For each position i > 0, we calculate:

1. For odd-length subarrays f[i]:

   • Take all even-length subarrays ending at i-1 and extend them by including arr[i] (they become odd)
   • The sum contribution from previous even-length subarrays is g[i-1]
   • Additionally, arr[i] appears in (i // 2) + 1 odd-length subarrays ending at position i
   • Formula: f[i] = g[i-1] + arr[i] * ((i // 2) + 1)

2. For even-length subarrays g[i]:

   • Take all odd-length subarrays ending at i-1 and extend them by including arr[i] (they become even)
   • The sum contribution from previous odd-length subarrays is f[i-1]
   • Additionally, arr[i] appears in (i + 1) // 2 even-length subarrays ending at position i
   • Formula: g[i] = f[i-1] + arr[i] * ((i + 1) // 2)

Computing the Answer:

As we compute f[i] for each position, we accumulate it into our answer since f[i] represents the sum of all odd-length subarrays ending at position i. The final answer is the sum of all f[i] values: ∑f[i] for i from 0 to n-1.

The time complexity is O(n) as we iterate through the array once, and the space complexity is O(n) for storing the f and g arrays.

Example Walkthrough

Let's walk through the solution with arr = [1, 4, 2, 5, 3].

We'll track two arrays:

• f[i]: sum of odd-length subarrays ending at position i
• g[i]: sum of even-length subarrays ending at position i

Initialization (i = 0):

• f[0] = arr[0] = 1 (only subarray is [1] with length 1, which is odd)
• g[0] = 0 (no even-length subarrays can end at position 0)
• Running answer = 1

Position i = 1 (arr[1] = 4):

• Calculate odd-length subarrays: f[1] = g[0] + arr[1] * ((1 // 2) + 1) = 0 + 4 * 1 = 4
  • This represents subarray [4] of length 1
• Calculate even-length subarrays: g[1] = f[0] + arr[1] * ((1 + 1) // 2) = 1 + 4 * 1 = 5
  • This represents subarray [1,4] of length 2, with sum = 1 + 4 = 5
• Running answer = 1 + 4 = 5

Position i = 2 (arr[2] = 2):

• Calculate odd-length subarrays: f[2] = g[1] + arr[2] * ((2 // 2) + 1) = 5 + 2 * 2 = 9
  • Previous even [1,4] becomes odd [1,4,2] (sum = 7)
  • Plus [2] itself (sum = 2)
  • Total: 7 + 2 = 9
• Calculate even-length subarrays: g[2] = f[1] + arr[2] * ((2 + 1) // 2) = 4 + 2 * 1 = 6
  • Previous odd [4] becomes even [4,2] (sum = 6)
• Running answer = 5 + 9 = 14

Position i = 3 (arr[3] = 5):

• Calculate odd-length subarrays: f[3] = g[2] + arr[3] * ((3 // 2) + 1) = 6 + 5 * 2 = 16
  • Previous even [4,2] becomes odd [4,2,5] (sum = 11)
  • Plus [5] itself (sum = 5)
  • Total: 11 + 5 = 16
• Calculate even-length subarrays: g[3] = f[2] + arr[3] * ((3 + 1) // 2) = 9 + 5 * 2 = 19
  • Previous odd [1,4,2] becomes even [1,4,2,5] (sum = 12)
  • Previous odd [2] becomes even [2,5] (sum = 7)
  • Total: 12 + 7 = 19
• Running answer = 14 + 16 = 30

Position i = 4 (arr[4] = 3):

• Calculate odd-length subarrays: f[4] = g[3] + arr[4] * ((4 // 2) + 1) = 19 + 3 * 3 = 28
  • Previous even [1,4,2,5] becomes odd [1,4,2,5,3] (sum = 15)
  • Previous even [2,5] becomes odd [2,5,3] (sum = 10)
  • Plus [3] itself (sum = 3)
  • Total: 15 + 10 + 3 = 28
• Calculate even-length subarrays: g[4] = f[3] + arr[4] * ((4 + 1) // 2) = 16 + 3 * 2 = 22
  • Previous odd [4,2,5] becomes even [4,2,5,3] (sum = 14)
  • Previous odd [5] becomes even [5,3] (sum = 8)
  • Total: 14 + 8 = 22
• Running answer = 30 + 28 = 58

Final Answer: 58

This represents the sum of all odd-length subarrays:

• Length 1: [1]=1, [4]=4, [2]=2, [5]=5, [3]=3 (sum = 15)
• Length 3: [1,4,2]=7, [4,2,5]=11, [2,5,3]=10 (sum = 28)
• Length 5: [1,4,2,5,3]=15 (sum = 15)
• Total: 15 + 28 + 15 = 58 ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. The algorithm iterates through the array once with a single for loop from index 1 to n-1, performing constant-time operations at each iteration (arithmetic operations and array accesses/assignments).

The space complexity is O(n), where n is the length of the array arr. The algorithm uses two auxiliary arrays f and g, each of size n, to store intermediate results. These arrays require 2n space, which simplifies to O(n) in big-O notation.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Count Calculation for Subarrays

The Pitfall: The most common mistake is incorrectly calculating how many times arr[i] appears in odd or even-length subarrays ending at position i. Developers often confuse the formulas:

• Using i // 2 instead of (i // 2) + 1 for odd-length subarrays
• Using i // 2 instead of (i + 1) // 2 for even-length subarrays

Why This Happens: The counting logic is counterintuitive. For position i, we need to count how many subarrays of a specific parity (odd/even) can end at that position. The formulas depend on whether i is even or odd itself.

Example of the Error:

# INCORRECT
odd_sum[i] = even_sum[i - 1] + arr[i] * (i // 2)  # Missing +1
even_sum[i] = odd_sum[i - 1] + arr[i] * (i // 2)  # Wrong formula

The Solution: Verify the count formulas by manually checking small examples:

• For odd-length subarrays at position i: count = (i // 2) + 1
• For even-length subarrays at position i: count = (i + 1) // 2

2. Space Optimization Confusion

The Pitfall: When optimizing space from O(n) to O(1), developers often forget to properly update the variables, leading to using stale values.

Example of the Error:

# INCORRECT space-optimized version
odd_sum = arr[0]
even_sum = 0
total = arr[0]

for i in range(1, n):
    odd_sum = even_sum + arr[i] * ((i // 2) + 1)  # even_sum gets overwritten below!
    even_sum = odd_sum + arr[i] * ((i + 1) // 2)  # Using NEW odd_sum, not previous!
    total += odd_sum

The Solution: Use temporary variables to store the new values:

odd_sum = arr[0]
even_sum = 0
total = arr[0]

for i in range(1, n):
    new_odd = even_sum + arr[i] * ((i // 2) + 1)
    new_even = odd_sum + arr[i] * ((i + 1) // 2)
    odd_sum = new_odd
    even_sum = new_even
    total += odd_sum

3. Alternative Approach Calculation Error

The Pitfall: When using the mathematical approach (counting how many times each element appears in all odd-length subarrays), developers often miscalculate the contribution formula.

Example of the Error:

# INCORRECT mathematical approach
for i in range(n):
    left_count = i + 1
    right_count = n - i
    # Forgetting to calculate odd-length combinations properly
    contribution = (left_count * right_count) // 2  # Wrong!

The Solution: The correct formula counts odd-length subarrays that include position i:

for i in range(n):
    left_odd = (i // 2) + 1
    left_even = (i + 1) // 2
    right_odd = ((n - i) // 2) + ((n - i) % 2)
    right_even = (n - i) // 2
  
    # Odd = odd*odd + even*even
    odd_count = left_odd * right_odd + left_even * right_even
    total += arr[i] * odd_count