# Sum of All Odd Length Subarrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-all-odd-length-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-all-odd-length-subarrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
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.

**Example 1:**

**Input:** arr = [1,4,2,5,3]
**Output:** 58
**Explanation:** The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
If we add all these together we get 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`

**Follow up:**

Could you solve this problem in O(n) time complexity?

# Approaches
## Brute Force Enumeration
This approach involves generating every possible subarray, checking if its length is odd, and if so, calculating its sum and adding it to a running total. It's the most straightforward but least efficient method, serving as a baseline.
**Time:** O(n^3), where n is the number of elements in the array. The three nested loops lead to a cubic time complexity. · **Space:** O(1), as we only use a constant amount of extra space for variables like `totalSum` and `currentSum`.
**Pros:** Very simple to understand and implement.; Directly follows the problem definition.
**Cons:** Extremely inefficient due to three nested loops.; Will result in a 'Time Limit Exceeded' error on larger inputs.
### Explanation
We use three nested loops. The outer two loops (with indices `i` and `j`) define the start and end of a subarray. For each subarray `arr[i...j]`, we first check if its length `(j - i + 1)` is odd. If it is, we use a third loop (with index `k`) to iterate from `i` to `j` to calculate the sum of its elements. This sum is then added to a grand total.
```java
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check if the length of the subarray is odd
                if ((j - i + 1) % 2 != 0) {
                    int currentSum = 0;
                    // Calculate the sum of the current subarray
                    for (int k = i; k <= j; k++) {
                        currentSum += arr[k];
                    }
                    totalSum += currentSum;
                }
            }
        }
        return totalSum;
    }
}
```
### Algorithm
- Initialize a variable `totalSum` to 0.
- Iterate through the array with an index `i` from 0 to `n-1` to select the starting element of the subarray.
-   Inside this loop, iterate with an index `j` from `i` to `n-1` to select the ending element of the subarray.
-     Calculate the length of the current subarray `arr[i...j]` as `j - i + 1`.
-     If the length is odd, proceed to calculate its sum.
-       Initialize `currentSum` to 0.
-       Iterate with an index `k` from `i` to `j` and add `arr[k]` to `currentSum`.
-       Add `currentSum` to `totalSum`.
- After all loops complete, return `totalSum`.

## Optimized Brute Force with Running Sum
This is an improvement over the pure brute-force method. Instead of recalculating the sum of each subarray from scratch, we can compute it more efficiently by maintaining a running sum as we extend the subarray.
**Time:** O(n^2), where n is the number of elements. The two nested loops result in quadratic time complexity. · **Space:** O(1), as we only use a constant amount of extra space.
**Pros:** More efficient than the O(n^3) approach.; Still relatively easy to understand and implement.; Passes the given constraints (n <= 100).
**Cons:** Not the most optimal solution.; Can be slow for larger inputs where n > 1000.
### Explanation
We use two nested loops. The outer loop (with index `i`) fixes the starting point of the subarrays. The inner loop (with index `j`) extends the subarray from `i` to `j`. As we extend the subarray by including `arr[j]`, we update a `currentSum`. For each new endpoint `j`, we have a new subarray `arr[i...j]` and its sum. We check if this subarray's length is odd. If it is, we add its `currentSum` to the `totalSum`. This eliminates the third loop used for summation, reducing the complexity from cubic to quadratic.
```java
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                // Extend the subarray and update the running sum
                currentSum += arr[j];
                // Check if the length is odd
                if ((j - i + 1) % 2 != 0) {
                    totalSum += currentSum;
                }
            }
        }
        return totalSum;
    }
}
```
### Algorithm
- Initialize `totalSum` to 0.
- Iterate through the array with an index `i` from 0 to `n-1` to fix the start of the subarray.
-   Initialize `currentSum` to 0 for subarrays starting at `i`.
-   Iterate with an index `j` from `i` to `n-1` to fix the end of the subarray.
-     Add `arr[j]` to `currentSum`. `currentSum` now holds the sum of `arr[i...j]`.
-     If the length `(j - i + 1)` is odd, add `currentSum` to `totalSum`.
- After the loops finish, return `totalSum`.

## Mathematical Approach using Contribution
This is the most optimal approach, solving the problem in linear time. Instead of iterating through subarrays, we consider each element `arr[i]` individually and calculate how many times it contributes to the final sum across all odd-length subarrays.
**Time:** O(n), as we iterate through the array only once. All calculations inside the loop are constant time. · **Space:** O(1), as we only use a few variables to store intermediate calculations.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for this problem.; Scales well for very large arrays.
**Cons:** The logic is less intuitive and requires some mathematical reasoning to derive the formula.
### Explanation
The core idea is to sum up the contributions of each element. For an element `arr[i]`, its total contribution is `arr[i]` multiplied by the number of odd-length subarrays that contain `arr[i]`.
To find this number, we observe:
- A subarray containing `arr[i]` must start at an index `s` where `0 <= s <= i` and end at an index `e` where `i <= e < n`.
- The number of possible starting positions is `left = i + 1`.
- The number of possible ending positions is `right = n - i`.
- The total number of subarrays containing `arr[i]` is `total_subarrays = left * right`.
- A key insight is that the number of odd-length subarrays containing `arr[i]` is `ceil(total_subarrays / 2.0)`, which can be calculated using integer arithmetic as `(total_subarrays + 1) / 2`.
We can iterate through the array once, calculate this contribution for each element, and add it to our total sum.
```java
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int totalSum = 0;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // Number of subarrays starting at or before index i
            int left = i + 1;
            // Number of subarrays ending at or after index i
            int right = n - i;
            // Total number of subarrays containing arr[i]
            int totalSubarrays = left * right;
            // Number of odd-length subarrays containing arr[i]
            int oddSubarrays = (totalSubarrays + 1) / 2;
            // Add the contribution of arr[i] to the total sum
            totalSum += oddSubarrays * arr[i];
        }
        return totalSum;
    }
}
```
### Algorithm
- Initialize `totalSum = 0` and `n = arr.length`.
- Iterate through the array with an index `i` from 0 to `n-1`.
-   For each element `arr[i]`:
-     Calculate the number of possible start indices: `left = i + 1`.
-     Calculate the number of possible end indices: `right = n - i`.
-     Calculate the total number of subarrays containing `arr[i]`: `total_subarrays = left * right`.
-     Calculate the number of odd-length subarrays containing `arr[i]`: `odd_subarrays = (total_subarrays + 1) / 2`.
-     Add the total contribution of this element to the sum: `totalSum += odd_subarrays * arr[i]`.
- After the loop, return `totalSum`.

# Solutions
### Java

```java
class Solution {
public
  int sumOddLengthSubarrays(int[] arr) {
    int n = arr.length;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int s = 0;
      for (int j = i; j < n; ++j) {
        s += arr[j];
        if ((j - i + 1) % 2 == 1) {
          ans += s;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int sumOddLengthSubarrays(vector<int> &arr) {
    int n = arr.size();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int s = 0;
      for (int j = i; j < n; ++j) {
        s += arr[j];
        if ((j - i + 1) & 1) {
          ans += s;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int: ans, n = 0, len(arr) for i in range(n): s = 0 for j in range(i, n): s += arr[j] if (j - i + 1) & 1: ans += s return ans

```