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.

Description Hints 1 Solution Video 15:38

1588. Sum of All Odd Length Subarrays

Easy84.0% acceptance3 companies

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?

Asked at 3 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

You can brute force – try every (i,j) pair, and if the length is odd, go through and add the sum to the answer.

15:38

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution