DEV Community

Cover image for Sum of All Odd Length Subarrays O(N) Leetcode #1588.
Rajesh Royal
Rajesh Royal

Posted on

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;
};

Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode
occurrances in only odd array = (currentIndex + 1) * (arrayLength - currentIndex) + 1) / 2
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

 

Thanks for reading. 🙋‍

Discussion (1)

Collapse
dingdingdong profile image
The D

It would be great if you give an example, and the expected output.