Sum of All Odd Length Subarrays

Sum of All Odd Length Subarrays

What is this problem about?

The "Sum of All Odd Length Subarrays" problem asks you to calculate the sum of all elements in every possible subarray of an array that has an odd length. A subarray is defined as a contiguous sequence of elements within the array. For example, in the array [1, 4, 2, 5, 3], odd-length subarrays include [1], [4], [2], [1, 4, 2], [4, 2, 5], and the entire array [1, 4, 2, 5, 3]. You must sum all elements from all these subarrays and return the total.

Why is this asked in interviews?

This "Easy" level question is a frequent flyer in interviews at Amazon, Google, and LinkedIn. It tests a candidate's ability to handle array indexing and nested loops efficiently. While a brute-force approach is often acceptable for smaller constraints, the problem also provides an opportunity for candidates to demonstrate their knowledge of "Contribution Technique"—calculating how many times each element appears in the final sum—which leads to a more optimized linear-time solution.

Algorithmic pattern used

There are two main patterns:

1. Brute Force (Nested Loops): Iterate through all possible starting points i and all odd lengths k, then sum the elements in arr[i...i+k].
2. Contribution Technique (Mathematical): For an element at index i, you calculate how many subarrays it belongs to. Specifically, how many odd-length subarrays? An element at index i is included in a subarray if the start index is ≤ i and the end index is ≥ i. By counting the combinations of even/odd prefixes and suffixes, you can find the exact number of times arr[i] contributes to the total sum in O(N) time.

Example explanation

Let's take arr = [1, 2, 3]. Odd-length subarrays:

• Length 1: [1], [2], [3]. Sums: 1, 2, 3.
• Length 3: [1, 2, 3]. Sum: 6. Total Sum = 1 + 2 + 3 + 6 = 12. Using the contribution technique:
• '1' is in [1] and [1,2,3]. (2 times)
• '2' is in [2] and [1,2,3]. (2 times)
• '3' is in [3] and [1,2,3]. (2 times) Sum = (12) + (22) + (3*2) = 2 + 4 + 6 = 12.

Common mistakes candidates make

1. Missing Subarrays: Failing to iterate correctly through all possible lengths (only doing length 1 or only the full array).
2. Redundant Calculations: In a brute-force approach, repeatedly summing the same elements instead of using a running total or prefix sums.
3. Index Out of Bounds: Incorrectly calculating the end index of a subarray, especially when dealing with the "odd length" constraint.

Interview preparation tip

Even if you solve an "Easy" problem with brute force, always ask the interviewer: "Would you like me to optimize this?" Explaining the contribution technique (how many subarrays contain this element) shows a higher level of mathematical maturity and algorithmic thinking.