LeetCode 1588 - Sum of All Odd Length Subarrays

LeetCode Problem 1588

Difficulty: 🟢 Easy
Topics: Array, Math, Prefix Sum

Solution

Problem Understanding

The problem asks us to calculate the sum of all odd-length subarrays of a given array of positive integers. A subarray is any contiguous sequence of elements from the original array. For example, in an array [1, 2, 3], the subarrays of length 1 are [1], [2], [3], and the subarray of length 3 is [1, 2, 3]. Odd-length subarrays are simply those whose lengths are 1, 3, 5, and so on.

The input arr is an array of integers where the length can range from 1 to 100, and each element is between 1 and 1000. The output should be a single integer representing the sum of all numbers in all odd-length subarrays.

The constraints suggest that a straightforward brute-force solution may work because the array size is relatively small, but the problem also asks if it can be solved in O(n) time for efficiency.

Edge cases include arrays of length 1, arrays where all elements are identical, and arrays where only one odd-length subarray exists. These could trip up naive implementations that assume multiple subarrays exist.

Approaches

Brute Force Approach

The brute-force approach iterates over all possible odd lengths from 1 up to the length of the array. For each length, we iterate over all starting indices of subarrays of that length, compute the sum, and accumulate it into a total. This works because we are explicitly visiting every subarray and summing its elements. The downside is that it requires nested loops, which can be inefficient for larger arrays. Specifically, this approach has O(n^3) complexity if we sum elements of each subarray in another loop, or O(n^2) if we use prefix sums.

Optimal Approach

The key insight for the optimal approach is combinatorial counting. Instead of explicitly summing every subarray, we calculate how many times each element arr[i] appears in odd-length subarrays. Consider an element at index i:

1. There are i + 1 possible starting positions for subarrays that include arr[i].
2. There are n - i possible ending positions for subarrays that include arr[i].
3. The total number of subarrays including arr[i] is (i + 1) * (n - i).
4. Half of these subarrays (rounded up) have odd length, so count = ((i + 1) * (n - i) + 1) // 2.

We can multiply arr[i] by this count and sum for all elements. This gives an O(n) solution without explicitly generating subarrays.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Iterates over all odd lengths and all subarrays
Optimal	O(n)	O(1)	Counts contribution of each element combinatorially

Algorithm Walkthrough

1. Initialize total_sum to 0. This will hold the cumulative sum of all odd-length subarrays.
2. Iterate over the array using index i and value num.
3. For each element, calculate the total number of subarrays that include it as (i + 1) * (n - i).
4. Compute how many of these subarrays have odd length using odd_count = (total_subarrays + 1) // 2.
5. Add num * odd_count to total_sum.
6. Return total_sum after processing all elements.

Why it works: Every element contributes to multiple subarrays. By counting the number of odd-length subarrays containing each element and multiplying by its value, we account for every subarray exactly once, ensuring correctness.

Python Solution

from typing import List

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total_sum = 0
        n = len(arr)
        for i, num in enumerate(arr):
            total_subarrays = (i + 1) * (n - i)
            odd_count = (total_subarrays + 1) // 2
            total_sum += num * odd_count
        return total_sum

In this Python implementation, we iterate through each element of the array. We compute how many subarrays include this element and determine how many of them are odd-length. Multiplying the element by this count accumulates its contribution to the total sum. Using integer division ensures rounding up correctly for odd counts.

Go Solution

func sumOddLengthSubarrays(arr []int) int {
    totalSum := 0
    n := len(arr)
    for i, num := range arr {
        totalSubarrays := (i + 1) * (n - i)
        oddCount := (totalSubarrays + 1) / 2
        totalSum += num * oddCount
    }
    return totalSum
}

In Go, we handle arrays with the same logic as Python. Integer division naturally truncates toward zero, so (totalSubarrays + 1) / 2 gives the correct count of odd-length subarrays.

Worked Examples

Example 1: [1,4,2,5,3]

i	num	total_subarrays	odd_count	contribution	total_sum
0	1	5	3	3	3
1	4	8	4	16	19
2	2	9	5	10	29
3	5	8	4	20	49
4	3	5	3	9	58

Output is 58.

Example 2: [1,2]

i	num	total_subarrays	odd_count	contribution	total_sum
0	1	2	1	1	1
1	2	2	1	2	3

Output is 3.

Example 3: [10,11,12]

i	num	total_subarrays	odd_count	contribution	total_sum
0	10	3	2	20	20
1	11	4	2	22	42
2	12	3	2	24	66

Output is 66.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array, constant-time calculation per element
Space	O(1)	Only a few variables are used, no extra data structures needed

The optimal approach scales linearly with array size, making it efficient even for the upper limit of 100 elements. The space usage is minimal since we only maintain counters.

Test Cases

# Provided examples
assert Solution().sumOddLengthSubarrays([1,4,2,5,3]) == 58  # Example 1
assert Solution().sumOddLengthSubarrays([1,2]) == 3         # Example 2
assert Solution().sumOddLengthSubarrays([10,11,12]) == 66   # Example 3

# Edge cases
assert Solution().sumOddLengthSubarrays([1]) == 1           # Single element
assert Solution().sumOddLengthSubarrays([5,5,5,5,5]) == 75  # All same elements
assert Solution().sumOddLengthSubarrays([1000]*100) == 2500000  # Max size, max value
assert Solution().sumOddLengthSubarrays([1,2,3,4,5,6]) == 56  # Even length array

Test	Why
[1,4,2,5,3]	Standard case with multiple odd-length subarrays
[1,2]	Array with length less than 3
[10,11,12]	Small odd-length array
[1]	Single element array edge case
[5,5,5,5,5]	Identical elements
[1000]*100	Stress test with maximum input values
[1,2,3,4,5,6]	Even-length array

Edge Cases

First, a single-element array like [1] is trivial but important. The code handles it because the combinatorial formula correctly counts that the single element is in one odd-length subarray.

Second, an array with all identical elements, such as [5,5,5,5,5], tests whether the algorithm correctly counts repeated contributions. Each element is multiplied by the number of odd-length subarrays that include it, and the sum correctly reflects repeated values.

Third, maximum input sizes with [1000]*100 confirm that the algorithm does not exceed time limits or integer overflow in languages like Go, since counts and products stay within reasonable integer bounds for the problem constraints.

These cases ensure robustness across minimal, typical, and maximal inputs.