We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of All Odd Length Subarrays

Number: 1693

Difficulty: Easy

Paid? No

Companies: Amazon, LinkedIn

Problem Description

Given an array of positive integers, return the sum of all possible odd-length subarrays. A subarray is a contiguous subsequence of the array.

Key Insights

  • Instead of iterating through all subarrays (which may be inefficient), determine how many odd-length subarrays each element participates in.
  • For an element at index i, compute:
    • left_count = number of elements (including itself) to its left, i.e. (i+1).
    • right_count = number of elements (including itself) to its right, i.e. (n-i).
  • The number of subarrays that include the element and have odd length is given by: (odd_left * odd_right + even_left * even_right) where:
    • odd_left = (left_count + 1) // 2, even_left = left_count // 2
    • odd_right = (right_count + 1) // 2, even_right = right_count // 2
  • Multiply the element’s value by its total count from odd-length subarrays to accumulate the result.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We use a combinatorial approach to count the number of odd-length subarrays that each element contributes to. For every index, compute the number of subarrays starting on the left and ending on the right that can include the current element. Then, use the parity counts (odd and even counts) on both sides to determine how many of these subarrays have odd length. Sum the product of each element's value with its corresponding count. This approach avoids enumerating all subarrays and runs in a single pass over the array.

Code Solutions

# Python solution for Sum of All Odd Length Subarrays

def sumOddLengthSubarrays(arr):
    total_sum = 0  # Initialize the total sum to 0
    n = len(arr)   # Get the length of the array
    
    # Iterate through each index and element in the array
    for i, num in enumerate(arr):
        # Count of elements on the left of current element (including itself)
        left_count = i + 1
        # Count of elements on the right of current element (including itself)
        right_count = n - i
        
        # Calculate number of ways to choose an odd count from left side
        odd_left = (left_count + 1) // 2
        even_left = left_count // 2
        
        # Calculate number of ways to choose an odd count from right side
        odd_right = (right_count + 1) // 2
        even_right = right_count // 2
        
        # Total number of odd-length subarrays including arr[i]
        subarrays_count = odd_left * odd_right + even_left * even_right
        
        # Add the contribution of the current element
        total_sum += num * subarrays_count
        
    return total_sum

# Example usage:
arr = [1,4,2,5,3]
print(sumOddLengthSubarrays(arr))  # Expected output: 58
← Back to All Questions