Problem Statement

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.

Input: arr = [1,4,2,5,3]
Output: 58

Explanation

Here we need to find the sum of the elements of all odd-length subarrays.

A subarray is the continous part of the array

Let's see what does it mean by odd-length subarray

Subarrays of arr = [1,4,2,5,3]
[1], [2], [3], [4], [5] -> subarray of length 1
[1,4], [4,2], [2,5], [5,3] -> subarray of length 2
[1,4,2], [4,2,5], [2,5,3] -> subarray of length 3
[1,4,2,5], [4,2,5,3] -> subarray of length 4
[1,4,2,5,3]-> subarray of length 5

Now we need to find the sum of an odd-length subarray i.e. the sum of a subarray of lengths 1, 3 and 5
1 + 2 + 3 + 4 + 5 = 15 -> sum of 1 length subarray
1+4+2 + 4+2+5 + 2+5+3 = 28 -> sum of 3 length subarray
1+4+2+5+3 = 15 -> sum of 5 length subarray
Final Sum = 15+28+15 = 58

Solution

Let's see how we can solve this

Brute Force Approach

• First what we do is we will use the logic of finding the subarrays in an array

for(int i=0; i<arr.length; ++i) {
    for(int j=i; j < arr.length; ++j) {
        for (int k=i; k<=j; ++k) {
            System.out.print(arr[k] + " ");
        }
        System.out.println();
    }
}

DRY RUN
arr = [1,4,2,5,3]
when i=0, j will traverse from 0 to 4
j=0, k=0 -> [1]
j=1, k=0,1 -> [1,4]
j=2, k=0,1,2 -> [1,4,2]
j=3, k=0,1,2,3 -> [1,4,2,5]
j=3, k=0,1,2,3,4 -> [1,4,2,5,3]

when i=1, j will traverse from 1 to 4
j=1, k=1 -> [4]
j=2, k=1,2 -> [4,2]
j=3, k=1,2,3 -> [4,2,5] and so on

• Now we need to identify the odd-length subarrays and find their sum

Let's take [1,4,2] & [1,4,2,5] subarrays, and let's see how can we find the size of this subarray. In the above code,
i -> is the start index of every subarray
j -> is the end index of every subarray
k -> elements from i to j

so if the size of the array is odd then we will find its sum

public int sumOddLengthSubarrays(int[] arr) {
    int sum=0;
      for (int i=0; i<arr.length; ++i) {
            for (int j=i; j<arr.length; ++j) {
                 for (int k=i; k<=j; ++k) {
                       if ((j-i+1)%2 != 0)
                             sum += arr[k];
                 }
            }
        }        
    return sum;
}

Time Complexity - O(n^3)
Space Complexity - O(1)

Optimized Solution

Let's take all the subarrays of arr = [1,4,2,5,3] by their length

observe 2 in odd-length subarrays, it is appearing 5 times means the sum of the odd length will contain the sum of these five 2's means we can write it as 5*2
Similarly,
element --> 1 4 2 5 3
times ---> 3 4 5 4 3
total ----> 3 16 10 20 9
on adding the total (element \ times)* values we get 58 which is the required number

 public int sumOddLengthSubarrays(int[] arr) {
        int result = 0;
        int n = arr.length;

        for (int i=0; i<n; i++) {
            int end = i+1;
            int start = n-i;
            int total = start*end;
            int odd = total / 2;

            if (total %2 == 1) {
                odd++;
            }
            result += odd * arr[i]; 
        }

        return result;
    }

Now before moving to the above code let's understand a concept

Suppose you have 3 chocolates and 2 toffies and I told you to pick up a pair of 1 chocolate and 1 toffy so in how many ways you can do it?

Let Chocolate -> A, B
Toffies -> C, D, E

Now you can choose A and then any of C, D, and E or you can choose B and any of the other three toffies
so there are 6 ways to choose a pair of chocolate and toffy

Similarly, suppose there are 5 subarrays that start with 0 and 1 sub-array which ends with 0
so the total no of subarrays will be 5*1 = 5

Now in the above code
start -> no. of subarrays starting with index i
end -> no of subarrays ending with index i
total -> total number of times i is coming in subarrays

you would be wondering why we did total/2 it's because total has all the subarrays having i so we divide it by 2, half of them will be in odd length array and half of them will be in even length array

In the above table of arr, 1 is in 5 subarrays and 2 of them are even length arrays while 3 of them are odd length arrays so if the total is a odd number we add +1 after dividing it by 2

if (total %2 == 1)
    odd++;
}

Time Complexity - O(n)
Space Complexity - O(1)

Thanks for reading this blog, I Hope it helped you in understanding the question better.
If you want more solutions like this then subscribe to my newsletter, I am making a series of DSA-Days in which I will post one solution a day of leetcode question. The series will cover all types of questions like Easy/Medium/Hard and they will be topic-wise.