Sum of All Odd Length Subarrays O(N) Leetcode #1588.

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

A subarray is a contiguous subsequence of the array.

Follow up:

Could you solve this problem in O(n) time complexity?

Below are the three approaches from brute force method to Best Case Runtime.

1. O(N^2 * log n)

var sumOddLengthSubarrays = function(arr) {
    let result = 0;
    for(let i = 0; i < arr.length; i++){
        result += arr[i]
    }

    for(let i = 0; i < arr.length; i++){
        for(let j = i + 2; j < arr.length; j += 2){
            for(let t = i; t <= j; t++){
                result += arr[t];
            }
        }
    }

    return result;
};

2. O(N^2)

var sumOddLengthSubarrays = function(arr) {
    let result = 0;
    let lastWindowSum = 0;
    for(let i = 0; i < arr.length; i++){
        result += arr[i]
    }

    for(let i = 0; i < arr.length; i++){
        for(let j = i + 2; j < arr.length; j += 2){

            // if this is the first time then add current start index to window sum.
            if(lastWindowSum === 0) lastWindowSum = arr[i];

            // memoized sum + next newly added elements only.
            result += lastWindowSum + arr[j] + arr[j - 1];

            // memoize the previous window sum
            lastWindowSum += arr[j] + arr[j - 1];
        }
        // reset last window when new window starts [the position of subarray starts change]
        lastWindowSum = 0;
    }

    return result;
};

3. O(N)

To solve this problem in O(N) time we have to calculate how many sub arrays from an index can be made, after that we devide it by 2 and get the odd sub arrays.

Once we have the number of odd sub arrays for an Index we can multiply this index witht the number of sub arrays to get final result of current index' sum.

To check how many times a number can appear in a subarray or that how many subarrays can be created with this current number we apply this below formulla.

total occurrances = (currentIndex + 1) * (arrayLength - currentIndex) + 1);

occurrances in only odd array = (currentIndex + 1) * (arrayLength - currentIndex) + 1) / 2

And to get the sum from the odd arrays we multiply the occurrance with current number.

sum in odd array = (currentIndex + 1) * (arrayLength - currentIndex) + 1) / 2 * currentNumber.

For JavaScript we have to parseInt - parseInt(((i + 1) * (arr.length - i) + 1) / 2) * arr[i]

var sumOddLengthSubarrays = function(arr) {
    let result = 0;

    for(let i = 0; i < arr.length; ++i) {
        result += parseInt(((i + 1) * (arr.length - i) + 1) / 2) * arr[i];
    }

    return result;
};

Thanks for reading. 🙋‍

Blog

Sum of All Odd Length Subarrays O(N) Leetcode #1588.

Rajesh Royal

1. O(N^2 * log n)

2. O(N^2)

3. O(N)

Join Our Newsletter. No Spam, Only the good stuff.

Related