Sum of All Odd Length Subarrays Leetcode
Input: Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.
Output: The sum of all possible odd-length subarrays of arr.
Let's start solving this problem.
First of all, let me tell you
NOT EVERY EASY-TAGGED PROBLEM IS EASY!!
Solution 1
Brute Force approach:
- Find every possible subarray of odd length.
- calculate the sum of this subarray, and add up the final sum.
- Time complexity: O(n³)
- Space complexity: O(1)
The Code goes here :
Solution 2
- Find every possible subarray of odd length.
- calculate the sum of this subarray while you traverse the subarray
- Time complexity: O(n²)
- Space complexity: O(1)
The code goes here :
Solution 3
Consider the contribution of every element of arr in finding the sum.
So, for that let's first calculate how many such subarrays are possible in which arr[i] is present. Suppose we could efficiently compute how many copies of each element there are across all the different subarrays. In that case, we could directly compute the sum by multiplying each component of the array by the number of times it appears across all the subarrays and then adding them up.
So, considering a subarray that contains arr[i], the left endpoint and right endpoint of the subarrays will be calculated as follows:
examples are:
let us first consider finding the contribution of each element to the total sum of the array, without exactly calculating the contribution in odd length subarray
arr = [1, 2, 3, 4]
possible subarrays are:
[1] , [1,2], [1, 2, 3], [1, 2, 3, 4]
[2], [2, 3], [2, 3, 4]
[3], [3,4]
[4]
There are two types of contributions of each element in a given subarray:
1. arr[i] is the first element of the subarray.
2. arr[i] is not the first element of the subarray
subarrays which begin with ith element are:
i=0, arr[i] = 1, subarrays beginning with 1 = 4
i=1, arr[i] = 2, subarrays beginning with 2 = 3
i=2, arr[i] = 3, subarrays beginning with 3= 2
i=3, arr[i] = 4, subarrays beginning with 4= 1
Hence, the subarrays beginning with ith element = n-i
Now, let us consider the subarrays where the ith element is not the first element
i=0, arr[i] = 1, subarrays not beginning with 1 = 0
i=1, arr[i] = 2, subarrays not beginning with 2= 3
i=2, arr[i] = 3, subarrays not beginning with 3= 4
i=3, arr[i]=4 , subarrays not beginning with 4 = 3
hence , let us conclude that the subarrays where ith element is not the first element will look something like this
0…….i, i+1, i+2…..n-1
leftendpoints can be = 0…..i-1
total left endpoints are = i-1–0+1 = i
rightendpoints = i+1,…….n
total right endpoints are = n-(i+1)+1 = n-i-1+1 = n-i
hence , total subarrays where ith element is not the first element is = total left endpoints * total right endpoints = i*(n-i)
HENCE , LETS SUM UP TOTAL CONTRIBUTION OF EACH ELEMENT
TOTAL CONTRIBUTION OF ith ELEMENT= (n-i) + (n-i)*i = (n-i)*(i+1)
The major task is done!!
Give yourself a pat on your back, if you reached here 😃
So, if you were asked for the total sum of all subarrays of the given array, then you can calculate by simply calculating the contribution of each element and summing it up together. This will have a time complexity of O(N) where N is the size of the given array.
Now, coming back to our original question.
We know total contribution of each element = (n-i)*(i+1) = say K
total odd length subarrays will be = (K+1)/2
total even length subarrays will be = K/2
so, calculating odd length subarrays and their sum will be
= ((n-i)*(i+1)+1)/2
Time complexity : O(N)
Space complexity : O(1)
So, I would say this was a great question!!
Let your brain neurons get stronger by making them work more!!
Push yourself a little more every day!!
