LeetCode 1588: Sum of All Odd Length Subarrays

Explanation:

• Algorithmic Idea:

  1. For each element in the array, we calculate the number of subarrays it can contribute to with odd length.
  2. The number of subarrays an element at index i can contribute to is (i + 1) * (n - i) where n is the length of the array.
  3. We iterate through the array, calculate the sum of each element multiplied by the number of subarrays it can contribute to, and sum them up.

• Time Complexity: O(n)

• Space Complexity: O(1)

:

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int sum = 0;
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            int contribution = (i + 1) * (n - i);
            sum += (contribution + 1) / 2 * arr[i];
        }
        
        return sum;
    }
}