1588. Sum of All Odd Length Subarrays

📝 Problem Details

• Title: 1588. Sum of All Odd Length Subarrays
• Link: https://leetcode.com/problems/sum-of-all-odd-length-subarrays/
• Difficulty: Easy
• Tags/Categories: Arrays Prefix-Sum

💡 Explanation of Solution

1. Calculate the Prefix Sum Array
	- the prefix sum array prefix[i] stores the sum of elements from teh start of the array to the index i
	- this allows quick computation of the sum of any subarray

2. Iterate Over All Subarrays
	- For each starting index `i`, iterate over possible ending indices `j` such that the subarray length `(j - i + 1)` is odd
	- Compute the sum of the subarray using the prefix sum array:
	- Otherwise: `sum = prefix[j] - prefix[i - 1]` 

3. Accumulate the Sum
	- Add the computed sum of each odd-length subarray to a running total

🧠 Example

arr = {1, 4, 2, 5, 3}

prefix = {1, 5, 7, 12, 15}

Subarrays of odd length:

- Length 1: {1}, {4}, {2}, {5}, {3}
- Length 3: {1, 4, 2}, {4, 2, 5}, {2, 5, 3}
- Length 5: {1, 4, 2, 5, 3}

Sum = 1 + 4 + 2 + 5 + 3 + (1+4+2) + (4+2+5) + (2+5+3) + (1+4+2+5+3) = 58

⌛ Complexity Analysis

Time Complexity: O(n^2)
	- constructing the prefix sum array takes O(n)
	- the nested loop over all subarrays takes O(n^2)
	- each subarray calculation is only O(1) due to the use of a prefix sum

Space Complexity: O(n) for the prefix sum array

💻 Implementation of Solution

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int n = arr.size();
        vector<int> prefix(n, 0);
        prefix[0] = arr[0];
 
        // Calculate prefix sum
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }
 
        int totalSum = 0;
 
        // Iterate over all possible subarrays
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Only consider subarrays of odd length
                if ((j - i + 1) % 2 == 1) {
                    // Calculate subarray sum using prefix sum
                    int subarraySum = (i == 0) ? prefix[j] : prefix[j] - prefix[i - 1];
                    totalSum += subarraySum;
                }
            }
        }
 
        return totalSum;
    }
};