Sum of All Odd Length Subarrays Solution

In this page, we will solve the Sum of All Odd Length Subarrays problem using multiple approaches: brute-force and prefix sum optimization. We will provide the implementation of the solution in Python, JavaScript, TypeScript, Java, and C++.

Problem Description

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.

A subarray is a contiguous subsequence of the array.

Return the sum of all odd-length subarrays of arr.

Examples

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 sum everything, 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 elements. So, only subarrays of length 1 and 2 will be considered. The sum of them is 1 + 2 = 3.

Example 3:

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

Constraints

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

---

Solution for Sum of All Odd Length Subarrays

Intuition and Approach

The problem can be solved using different approaches. We will start with a brute-force approach and then look at an optimized approach using prefix sums.

• Brute Force
• Prefix Sum

Approach 1: Brute Force

We iterate through all possible subarrays of odd lengths and calculate their sums.

Implementation

Live Editor

function sumOfOddLengthSubarrays() {
  const arr = [1, 4, 2, 5, 3];

  const sumOddLengthSubarrays = function(arr) {
    let result = 0;
    for (let i = 0; i < arr.length; i++) {
      for (let j = i; j < arr.length; j += 2) {
        for (let k = i; k <= j; k++) {
          result += arr[k];
        }
      }
    }
    return result;
  };

  const result = sumOddLengthSubarrays(arr);
  return (
    <div>
      <p>
        <b>Input:</b> arr = {JSON.stringify(arr)}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}

Result

Loading...

Codes in Different Languages

JavaScript

Written by @manishh12

 function sumOddLengthSubarrays(arr) {
   let result = 0;
   for (let i = 0; i < arr.length; i++) {
     for (let j = i; j < arr.length; j += 2) {
       for (let k = i; k <= j; k++) {
         result += arr[k];
       }
     }
   }
   return result;
 }

TypeScript

Written by @manishh12

 function sumOddLengthSubarrays(arr: number[]): number {
   let result = 0;
   for (let i = 0; i < arr.length; i++) {
     for (let j = i; j < arr.length; j += 2) {
       for (let k = i; k <= j; k++) {
         result += arr[k];
       }
     }
   }
   return result;
 }

Python

Written by @manishh12

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

Java

Written by @manishh12

 class Solution {
     public int sumOddLengthSubarrays(int[] arr) {
         int result = 0;
         for (int i = 0; i < arr.length; i++) {
             for (int j = i; j < arr.length; j += 2) {
                 for (int k = i; k <= j; k++) {
                     result += arr[k];
                 }
             }
         }
         return result;
     }
 }

C++

Written by @manishh12

 class Solution {
 public:
     int sumOddLengthSubarrays(vector<int>& arr) {
         int result = 0;
         for (int i = 0; i < arr.size(); i++) {
             for (int j = i; j < arr.size(); j += 2) {
                 for (int k = i; k <= j; k++) {
                     result += arr[k];
                 }
             }
         }
         return result;
     }
 };

Complexity Analysis

• Time Complexity: $O(n^3)$
• Space Complexity: $O(1)$
• Where n is the length of the array arr.
• The time complexity is cubic due to three nested loops iterating through the array.
• The space complexity is constant as no additional space is required beyond a few variables.

Note

By using these approaches, we can efficiently solve the Sum of All Odd Length Subarrays problem for the given constraints.

References

• LeetCode Problem: LeetCode Problem
• Solution Link: Sum of All Odd Length Subarrays Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta