LeetCode 1588. Sum of All Odd Length Subarrays

Description

https://leetcode.com/problems/sum-of-all-odd-length-subarrays/

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.

A subarray is a contiguous subsequence of the array.

Return the sum of all odd-length subarrays of arr.

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

Explanation

Iterate all the odds lengths which are shorter than the array length. And find all the sub array at each odd length and sum the sum array up.

Python Solution

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        
        sub_size = 1
        
        result = 0
        
        while sub_size <= n:
            
            for i in range(0, len(arr) - sub_size + 1):
                sub = arr[i : i + sub_size]
                result += sum(sub)
                        
            sub_size += 2
        
        return result