Sum of All Odd Length Subarrays solution and explanation
Google
9 more videos on this problem
Sum of All Odd Length Subarrays | LeetCode 1588 | Explained and Java CodeNate Santti · 15:38 · 37K views
Leetcode 1588. Sum of All Odd Length Subarrays - O(n)Kacy Codes · 7:06 · 8K views
LeetCode 1588. [easy] Sum of All Odd Length SubarraysFrancesco Manicardi · 4:11 · 6K views
1588. Sum of All Odd Length Subarrays (Leetcode Easy)Programming Live with Larry · 3:02 · 4K views
Sum of All Odd Length Subarrays - Leetcode 1588 - PythonStreet Coder · 9:23 · 3K views
Leetcode Sum of All Odd Length Subarrays | Beginner-Friendly Step by Step WalkthroughLearnWithDnyanesh · 14:31 · 1K views
LeetCode 1588 | Sum of All Odd Length Subarrays | Math | JavaSleepy Cracker · 4:53 · 877 views
Episode 51 | Leetcode | Hindi and English | Sum of All Odd Length SubarraysLet's Leet · 4:55 · 742 views
1588 Sum of All Odd Length Subarrays - leetcode (Java) Dynamic ProgrammingSloppy Guy · 15:16 · 725 views
L-62 | Sum of All Odd Length Subarrays | LeetCode - 1588 | Easy | Intuition | Aditya GoyalAditya Goyal · 17:35 · 689 views
The 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 <= 1001 <= arr[i] <= 1000
Follow up:
Could you solve this problem in O(n) time complexity?
Approach overview
Problem Overview: You are given an integer array and must compute the total sum of every subarray whose length is odd. Each valid subarray contributes the sum of its elements to the final result, so the task is to efficiently enumerate or calculate these contributions without redundant work.
Approach 1: Brute Force Enumeration (Time: O(n^3), Space: O(1))
The most direct solution iterates over every possible subarray and checks whether its length is odd. Use two nested loops to choose the start and end indices, then compute the subarray sum with a third loop. If (end - start + 1) is odd, add the sum to the result. This approach clearly demonstrates the problem mechanics: generate subarrays, validate length, accumulate values. However, repeated summation of overlapping ranges causes heavy redundancy, making it inefficient for larger inputs.
Approach 2: Mathematical Contribution Counting (Time: O(n), Space: O(1))
The optimal insight comes from counting how many odd-length subarrays include each element. For an index i, there are (i + 1) ways to choose a starting position to the left and (n - i) ways to choose an ending position to the right. Multiplying these gives the total number of subarrays containing that element. Only half of those will have odd length. The exact count is ((i + 1) * (n - i) + 1) // 2. Multiply this frequency by arr[i] and accumulate the result. This converts the problem from enumerating subarrays to counting element contributions.
This approach is essentially a counting trick built on properties of array indices and parity. Instead of explicitly forming subarrays, you compute how often each value appears in valid odd-length windows. The algorithm performs a single pass through the array and requires constant extra memory.
Although the problem can also be reasoned about using cumulative sums similar to prefix sum techniques, the contribution formula derived from simple math reasoning gives the cleanest O(n) implementation.
Recommended for interviews: The mathematical contribution approach is what interviewers typically expect. Starting with the brute force method shows you understand subarray generation and the constraint on odd lengths. Deriving the contribution formula demonstrates deeper algorithmic thinking and reduces the complexity from O(n^3) to O(n) with constant space.
Approach 1: Brute Force Approach
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.
def sumOddLengthSubarrays(arr):
total_sum = 0
n = len(arr)
for start in range(n):
for end in range(start, n):
if (end - start + 1) % 2 != 0:
total_sum += sum(arr[start:end+1])
return total_sum
arr = [1, 4, 2, 5, 3]
print(sumOddLengthSubarrays(arr))public class Main {
public static int sumOddLengthSubarrays(int[] arr) {
int totalSum = 0;
int n = arr.length;
for (int start = 0; start < n; ++start) {
for (int end = start; end < n; ++end) {
if ((end - start + 1) % 2 != 0) {
for (int k = start; k <= end; ++k) {
totalSum += arr[k];
}
}
}
}
return totalSum;
}
public static void main(String[] args) {
int[] arr = {1, 4, 2, 5, 3};
System.out.println(sumOddLengthSubarrays(arr));
}
}#include <iostream>
#include <vector>
using namespace std;
int sumOddLengthSubarrays(vector<int>& arr) {
int totalSum = 0, n = arr.size();
for (int start = 0; start < n; ++start) {
for (int end = start; end < n; ++end) {
if ((end - start + 1) % 2 != 0) {
for (int k = start; k <= end; ++k) {
totalSum += arr[k];
}
}
}
}
return totalSum;
}
int main() {
vector<int> arr = {1, 4, 2, 5, 3};
cout << sumOddLengthSubarrays(arr) << endl;
return 0;
}function sumOddLengthSubarrays(arr) {
let totalSum = 0;
const n = arr.length;
for (let start = 0; start < n; ++start) {
for (let end = start; end < n; ++end) {
if ((end - start + 1) % 2 !== 0) {
for (let k = start; k <= end; ++k) {
totalSum += arr[k];
}
}
}
}
return totalSum;
}
const arr = [1, 4, 2, 5, 3];
console.log(sumOddLengthSubarrays(arr));#include <stdio.h>
int sumOddLengthSubarrays(int *arr, int arrSize) {
int totalSum = 0;
for (int start = 0; start < arrSize; start++) {
for (int end = start; end < arrSize; end++) {
if ((end - start + 1) % 2 != 0) {
for (int k = start; k <= end; k++) {
totalSum += arr[k];
}
}
}
}
return totalSum;
}
int main() {
int array[] = {1, 4, 2, 5, 3};
int result = sumOddLengthSubarrays(array, 5);
printf("%d\n", result);
return 0;
}using System;
class Program {
static int SumOddLengthSubarrays(int[] arr) {
int totalSum = 0, n = arr.Length;
for (int start = 0; start < n; ++start) {
for (int end = start; end < n; ++end) {
if ((end - start + 1) % 2 != 0) {
for (int k = start; k <= end; ++k) {
totalSum += arr[k];
}
}
}
}
return totalSum;
}
static void Main() {
int[] arr = {1, 4, 2, 5, 3};
Console.WriteLine(SumOddLengthSubarrays(arr));
}
}Python offers an elegant solution by using list comprehension and built-in sum function. The code iterates over all possible subarrays and calculates their sums if the length is odd.
Time Complexity: O(n^3) due to slicing and summing operations.
Space Complexity: O(1) aside from input data.
Approach 2: Optimized Mathematical Approach
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.
def sumOddLengthSubarrays(arr):
total_sum = 0
n = len(arr)
for i in range(n):
leftCount = i + 1
rightCount = n - i
oddCount = (leftCount * rightCount + 1) // 2
total_sum += oddCount * arr[i]
return total_sum
arr = [1, 4, 2, 5, 3]
print(sumOddLengthSubarrays(arr))public class Main {
public static int sumOddLengthSubarrays(int[] arr) {
int totalSum = 0;
int n = arr.length;
for (int i = 0; i < n; i++) {
int leftCount = i + 1;
int rightCount = n - i;
int oddCount = (leftCount * rightCount + 1) / 2;
totalSum += oddCount * arr[i];
}
return totalSum;
}
public static void main(String[] args) {
int[] arr = {1, 4, 2, 5, 3};
System.out.println(sumOddLengthSubarrays(arr));
}
}#include <iostream>
#include <vector>
using namespace std;
int sumOddLengthSubarrays(vector<int>& arr) {
int totalSum = 0, n = arr.size();
for (int i = 0; i < n; i++) {
int leftCount = i + 1;
int rightCount = n - i;
int oddCount = (leftCount * rightCount + 1) / 2;
totalSum += oddCount * arr[i];
}
return totalSum;
}
int main() {
vector<int> arr = {1, 4, 2, 5, 3};
cout << sumOddLengthSubarrays(arr) << endl;
return 0;
}function sumOddLengthSubarrays(arr) {
let totalSum = 0;
const n = arr.length;
for (let i = 0; i < n; ++i) {
const leftCount = i + 1;
const rightCount = n - i;
const oddCount = ((leftCount * rightCount + 1) / 2) | 0;
totalSum += oddCount * arr[i];
}
return totalSum;
}
const arr = [1, 4, 2, 5, 3];
console.log(sumOddLengthSubarrays(arr));#include <stdio.h>
int sumOddLengthSubarrays(int *arr, int arrSize) {
int totalSum = 0;
for (int i = 0; i < arrSize; i++) {
int leftCount = i + 1;
int rightCount = arrSize - i;
int oddCount = (leftCount * rightCount + 1) / 2;
totalSum += oddCount * arr[i];
}
return totalSum;
}
int main() {
int array[] = {1, 4, 2, 5, 3};
int result = sumOddLengthSubarrays(array, 5);
printf("%d\n", result);
return 0;
}using System;
class Program {
static int SumOddLengthSubarrays(int[] arr) {
int totalSum = 0;
int n = arr.Length;
for (int i = 0; i < n; i++) {
int leftCount = i + 1;
int rightCount = n - i;
int oddCount = (leftCount * rightCount + 1) / 2;
totalSum += oddCount * arr[i];
}
return totalSum;
}
static void Main() {
int[] arr = {1, 4, 2, 5, 3};
Console.WriteLine(SumOddLengthSubarrays(arr));
}
}For Python, the approach remains concise, computing element contributions with arithmetic solutions for heightened efficiency and direct sum calculation.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Dynamic Programming (Space Optimization)
We notice that the values of f[i] and g[i] only depend on f[i - 1] and g[i - 1]. Therefore, we can use two variables f and g to record the values of f[i - 1] and g[i - 1], respectively, thus optimizing the space complexity.
The time complexity is O(n), and the space complexity is O(1).
function sumOddLengthSubarrays(arr: number[]): number {
const n = arr.length;
let [ans, f, g] = [arr[0], arr[0], 0];
for (let i = 1; i < n; ++i) {
const ff = g + arr[i] * (Math.floor(i / 2) + 1);
const gg = f + arr[i] * Math.floor((i + 1) / 2);
[f, g] = [ff, gg];
ans += f;
}
return ans;
}func sumOddLengthSubarrays(arr []int) (ans int) {
f, g := arr[0], 0
ans = f
for i := 1; i < len(arr); i++ {
ff := g + arr[i]*(i/2+1)
gg := f + arr[i]*((i+1)/2)
f, g = ff, gg
ans += f
}
return
}impl Solution {
pub fn sum_odd_length_subarrays(arr: Vec<i32>) -> i32 {
let mut ans = arr[0];
let mut f = arr[0];
let mut g = 0;
for i in 1..arr.len() {
let ff = g + arr[i] * ((i as i32) / 2 + 1);
let gg = f + arr[i] * (((i + 1) as i32) / 2);
f = ff;
g = gg;
ans += f;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) due to slicing and summing operations. Space Complexity: O(1) aside from input data. |
| Optimized Mathematical Approach | Time Complexity: O(n). Space Complexity: O(1). |
| Dynamic Programming (Space Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n^3) | O(1) | Useful for understanding how subarrays are generated and validating the odd-length constraint |
| Mathematical Contribution Counting | O(n) | O(1) | Best general solution; counts how many odd-length subarrays include each element |
Frequently asked questions
Is Sum of All Odd Length Subarrays easy or hard?
Sum of All Odd Length Subarrays is rated Easy on LeetCode with a high acceptance rate. The brute-force idea is straightforward, but recognizing the O(n) mathematical contribution approach demonstrates stronger algorithmic insight.
How to solve Sum of All Odd Length Subarrays in O(n)?
Iterate through the array and compute how many odd-length subarrays contain each element. For position i, compute total subarrays including that element as (i + 1) * (n - i). Half of those, rounded up, have odd length. Multiply that count by arr[i] and add it to the answer while scanning the array once.
Sum of All Odd Length Subarrays Python or Java solution?
Python and Java implementations follow the same idea: loop through the array, compute ((i + 1) * (n - i) + 1) // 2 to determine how many odd-length subarrays include arr[i], then accumulate arr[i] multiplied by that count. The logic is identical across Python, Java, C++, and other languages.
What is the best approach for Sum of All Odd Length Subarrays?
The best approach uses a mathematical contribution formula that counts how many odd-length subarrays include each element. For index i, there are (i + 1) possible starts and (n - i) possible ends, and roughly half of these combinations produce odd lengths. The element contributes arr[i] * (((i + 1) * (n - i) + 1) // 2) to the final sum. This yields an O(n) time and O(1) space solution.
What data structure is used in Sum of All Odd Length Subarrays?
The problem primarily uses arrays and basic arithmetic reasoning. The optimal solution relies on mathematical counting of index combinations rather than additional data structures, though the concept relates to prefix-sum style reasoning about subarray ranges.
What is the time complexity of Sum of All Odd Length Subarrays?
The optimal solution runs in O(n) time with O(1) extra space because each element's contribution is computed in constant time during a single pass through the array. A naive brute force solution that enumerates and sums every odd-length subarray takes O(n^3) time.
Is Sum of All Odd Length Subarrays asked at Google, Amazon, or Meta?
Sum of All Odd Length Subarrays is categorized as an Easy array and math problem but still appears in interview preparation sets for companies like Amazon and Google. It tests whether candidates recognize contribution counting patterns instead of brute-force enumeration.