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 <= 1001 <= arr[i] <= 1000
Follow up:
Could you solve this problem in O(n) time complexity?
The brute force approach involves iterating over every possible subarray, checking if its length is odd, and then summing its elements. This approach is straightforward but not optimal.
This C program utilizes nested loops to generate subarrays. The outer two loops iterate through all start and end indices. The innermost loop sums the elements of the current subarray if its length is odd.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3) where n is the number of elements in the array, due to triple nested loops.
Space Complexity: O(1), only a few extra variables are utilized.
The optimized approach calculates the contribution of each element to the final sum using a mathematical formula. For each element at index i, calculate how many odd-length subarrays it can contribute to, then sum directly based on these contributions.
This solution computes the contribution of each element to possible odd-length subarrays using a mathematical formula. For each element, calculate how many subarrays include the element, split this into odd/even counts, and then use that to determine its overall contribution to the sum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), much improved by calculating contributions directly.
Space Complexity: O(1), only a few extra integer variables.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) where n is the number of elements in the array, due to triple nested loops. Space Complexity: O(1), only a few extra variables are utilized. |
| Optimized Mathematical Approach | Time Complexity: O(n), much improved by calculating contributions directly. Space Complexity: O(1), only a few extra integer variables. |
Sum of All Odd Length Subarrays | LeetCode 1588 | Explained and Java Code • Nate Santti • 34,423 views views
Watch 9 more video solutions →Practice Sum of All Odd Length Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor