1588. Sum of All Odd Length Subarrays LeetCode Solution
In this guide, you will get 1588. Sum of All Odd Length Subarrays LeetCode Solution with the best time and space complexity. The solution to Sum of All Odd Length Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Sum of All Odd Length Subarrays
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?
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1588. Sum of All Odd Length Subarrays LeetCode Solution in C++
class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {
int ans = 0;
// Maintain two sums of subarrays ending in the previous index.
// Each time we meet a new number, we'll consider "how many times" it should
// contribute to the newly built subarrays by calculating the number of
// previous even/odd-length subarrays.
int prevEvenSum = 0; // the sum of even-length subarrays
int prevOddSum = 0; // the sum of odd-length subarrays
for (int i = 0; i < arr.size(); ++i) {
// (i + 1) / 2 := the number of previous odd-length subarrays.
const int currEvenSum = prevOddSum + ((i + 1) / 2) * arr[i];
// i / 2 + 1 := the number of previous even-length subarrays
// (including 0).
const int currOddSum = prevEvenSum + (i / 2 + 1) * arr[i];
ans += currOddSum;
prevEvenSum = currEvenSum;
prevOddSum = currOddSum;
}
return ans;
}
}; /* code provided by PROGIEZ */
1588. Sum of All Odd Length Subarrays LeetCode Solution in Java
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int ans = 0;
// Maintain two sums of subarrays ending in the previous index.
// Each time we meet a new number, we'll consider "how many times" it should
// contribute to the newly built subarrays by calculating the number of
// previous even/odd-length subarrays.
int prevEvenSum = 0; // the sum of even-length subarrays
int prevOddSum = 0; // the sum of odd-length subarrays
for (int i = 0; i < arr.length; ++i) {
// (i + 1) / 2 := the number of previous odd-length subarrays.
final int currEvenSum = prevOddSum + ((i + 1) / 2) * arr[i];
// i / 2 + 1 := the number of previous even-length subarrays
// (including 0).
final int currOddSum = prevEvenSum + (i / 2 + 1) * arr[i];
ans += currOddSum;
prevEvenSum = currEvenSum;
prevOddSum = currOddSum;
}
return ans;
}
} // code provided by PROGIEZ
1588. Sum of All Odd Length Subarrays LeetCode Solution in Python
class Solution:
def sumOddLengthSubarrays(self, arr: list[int]) -> int:
ans = 0
# Maintain two sums of subarrays ending in the previous index.
# Each time we meet a new number, we'll consider 'how many times' it should
# contribute to the newly built subarrays by calculating the number of
# previous even/odd-length subarrays.
prevEvenSum = 0 # the sum of even-length subarrays
prevOddSum = 0 # the sum of odd-length subarrays
for i, a in enumerate(arr):
# (i + 1) // 2 := the number of previous odd-length subarrays.
currEvenSum = prevOddSum + ((i + 1) // 2) * a
# i // 2 + 1 := the number of previous even-length subarrays
# (including 0).
currOddSum = prevEvenSum + (i // 2 + 1) * a
ans += currOddSum
prevEvenSum = currEvenSum
prevOddSum = currOddSum
return ans # code by PROGIEZ
