Sum of All Odd Length Subarrays

To solve this problem, we can use a simple approach of generating all possible subarrays with odd length and adding their sum.

Here is the Python solution:

1
2
3
4
5
6
7
8

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        n = len(arr)
        for l in range(1, n+1, 2):
            for i in range(n-l+1):
                total += sum(arr[i:i+l])
        return total

In this code, we use two loops. The outer loop is to control the length of the subarray (only odd lengths are considered, hence range(1, n+1, 2)) and the inner loop is to slide this subarray window across the given array. For each subarray, we calculate the sum of its elements and add it to the total sum. We return the total sum after traversing all possible odd-length subarrays.

Please note that this solution has time complexity of O(n^2) which is acceptable as per the problem constraints. However, there are more optimized solutions available using prefix sum and mathematical properties, if required.

The brute force solution to this problem is to generate all subarrays of the input array, calculate the sum for each, and then add up the sums of those that have an odd length.

Here is how it would look:

  1. Initialize a variable, total, to 0.
  2. For each starting index i from 0 to n-1, where n is the length of the array:
    • For each ending index j from i to n-1:
      • If the length of the subarray from index i to j (inclusive) is odd, calculate the sum of the elements in this subarray and add it to total.
  3. Return total.

This solution will indeed give us the correct result, but its time complexity is O(n^3) as there are n^2 subarrays and we are spending O(n) time to calculate the sum for each. This is not an efficient approach when the size of the array is large.

The solution provided earlier is an optimized version of the brute force approach. It reduces the time complexity to O(n^2) by calculating the sums of the subarrays in constant time using the built-in sum function. It does this by taking advantage of the fact that subarrays starting at the same index have overlapping elements.