algoadvance

Leetcode 1588. Sum of All Odd Length Subarrays Sure! Let’s solve the problem of finding the sum of all odd length subarrays in C++.

Problem Statement

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

An odd-length subarray is an array subsegment (contiguous subarray) of odd length.

Example:

Explanation:

Total = 15 + 28 + 15 = 58

Clarifying Questions

Before proceeding, let’s clarify a few things:

  1. What is the maximum size of the array?
  2. Are the elements all positive?
  3. Should the function handle edge cases like an empty array?

Let’s assume the array size is reasonable (up to 1000 elements) and all elements are positive integers. The function doesn’t need to handle an empty array since it wasn’t specified in the example.

Strategy

  1. Initialize a variable to store the sum.
  2. Iterate through all possible starting indices for subarrays.
  3. For each starting index, iterate over all possible ending indices such that the subarray length is odd.
  4. Calculate the sum of these subarrays and add it to the result variable.

Code

Here’s the implementation of the strategy described above in C++:

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int totalSum = 0;
        int n = arr.size();
        
        // Traverse each starting point of subarray
        for(int start = 0; start < n; ++start) {
            // Proceed to each subarray ending point from the starting point
            for(int end = start; end < n; ++end) {
                // Check if the length of the subarray is odd
                if ((end - start + 1) % 2 != 0) {
                    // Calculate sum of the current subarray
                    for(int i = start; i <= end; ++i) {
                        totalSum += arr[i];
                    }
                }
            }
        }

        return totalSum;
    }
};

int main() {
    Solution sol;
    vector<int> arr = {1, 4, 2, 5, 3};
    cout << sol.sumOddLengthSubarrays(arr) << endl;  // Output: 58
    return 0;
}

Time Complexity

The time complexity of the solution is (O(n^3)). Here’s why:

Thus, overall the complexity is (O(n^3)). This might not be optimal for larger arrays.

Possible Optimization

An optimization to consider reduces the problem from (O(n^3)) to (O(n^2)):

Would you like me to proceed with the optimized approach?

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI