Abstract / Summary

Find the sum of all elements in all odd length subarrays of a given array.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 84% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Math
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method sumOddLengthSubarrays that computes the sum of all subarrays of an input list arr whose lengths are odd. The algorithm iterates over every possible starting index, builds cumulative sums for subarrays that begin at that index, and selectively adds those sums to the final result when the subarray length is odd. By using a running total (current) for each start position, the code avoids recomputing the sum of a subarray from scratch, which yields a more efficient traversal of the input.

Core Logic

The outer loop selects each possible starting position i in the array. For each i, a variable current is reset to zero. This variable accumulates the sum of elements as the inner loop extends the subarray one element at a time.

for i in range(len(arr)):
    current = 0
    ...

The inner loop runs over the remaining elements from the start index i. The index j represents the offset from i, and the element at position i + j is added to current. This incremental addition means that the sum of the subarray [i, i + j] is available immediately after the update.

for j in range(len(arr) - i):
    current += arr[i + j]
    ...

The condition (j & 1) == 0 checks whether j is even. Since the length of the subarray is j + 1, an even offset corresponds to an odd length. When this condition holds, the accumulated sum current is added to the overall result.

if (j & 1) == 0:  # if j is even then the length is odd
    result += current

Finally, after all start positions have been processed, the method returns the accumulated result.

return result

Edge Cases Handled

When the input list is empty, the outer loop does not execute because range(len(arr)) yields no values. Consequently, result remains zero and the method returns zero, which correctly represents the sum of odd-length subarrays for an empty collection.

If the list contains a single element, the outer loop runs once with i = 0. The inner loop runs once with j = 0, current becomes the value of that element, the condition (j & 1) == 0 is true, and the element is added to result. The method therefore returns the element itself, matching the expected sum of the only odd-length subarray.

For lists with repeated values or negative numbers, the cumulative addition current += arr[i + j] correctly aggregates the signed values, and the selective addition to result respects the odd-length constraint without any special handling. The bitwise check works uniformly for any integer offset, ensuring consistent behavior across all possible subarray lengths.

Performance Optimizations

The algorithm leverages a running cumulative sum (current) for each starting index rather than recomputing the sum of each subarray from scratch. By updating current incrementally as the inner loop progresses, the code reduces the number of arithmetic operations required for overlapping subarrays. This approach eliminates the need for an inner nested loop that would otherwise sum each subarray element by element, thereby cutting down redundant work.

The use of a bitwise AND operation (j & 1) to test the parity of j is a low-level optimization compared to a modulo operation. Bitwise checks are typically faster because they operate directly on the binary representation of the integer, allowing the condition to be evaluated with minimal overhead.

Resetting current at the start of each outer iteration ensures that the cumulative sum is scoped to the current starting position, preventing the need for additional data structures to track partial sums across different start indices. This in-place accumulation keeps memory usage minimal and avoids the overhead of allocating auxiliary arrays.

Imagine a long train made of many colorful toy cars. Each car has a number on it. This set of instructions is like a game to find all the smaller parts of the train that have an odd number of cars. An odd number is just a number like one, three, or five, where you cannot split the cars into two equal groups without one left over.

The computer starts at the first car and slowly walks down the line. It picks up one car, then two, then three, adding up all the numbers painted on them. Every time the number of cars held in its hand is odd, it remembers the total sum of those numbers by tucking it into a special box called result. It repeats this for every place where a group of cars could start. By the time it reaches the very last car, all those little sums from the odd-sized groups are added together to make one big final number.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go		C	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem					Ruby
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	muhammadfarhankt						Go
	suxrobGM							C#
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality