Scale Engineer

Sum of All Odd Length Subarrays

Easy
#1460Time: O(n^3), where n is the number of elements in the array. The three nested loops lead to a cubic time complexity.Space: O(1), as we only use a constant amount of extra space for variables like `totalSum` and `currentSum`.
Patterns
MathPrefix Sum
Data structures
Array

Prompt

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.

 

Example 1:

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]
Output: 66

 

Constraints:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000

 

Follow up:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible subarray, checking if its length is odd, and if so, calculating its sum and adding it to a running total. It's the most straightforward but least efficient method, serving as a baseline.

Algorithm

  • Initialize a variable totalSum to 0.
  • Iterate through the array with an index i from 0 to n-1 to select the starting element of the subarray.
  • Inside this loop, iterate with an index j from i to n-1 to select the ending element of the subarray.
  • Calculate the length of the current subarray `arr[i...j]` as `j - i + 1`.
  • If the length is odd, proceed to calculate its sum.
  • Initialize `currentSum` to 0.
  • Iterate with an index `k` from `i` to `j` and add `arr[k]` to `currentSum`.
  • Add `currentSum` to `totalSum`.
  • After all loops complete, return totalSum.

Walkthrough

We use three nested loops. The outer two loops (with indices i and j) define the start and end of a subarray. For each subarray arr[i...j], we first check if its length (j - i + 1) is odd. If it is, we use a third loop (with index k) to iterate from i to j to calculate the sum of its elements. This sum is then added to a grand total.

class Solution {    public int sumOddLengthSubarrays(int[] arr) {        int n = arr.length;        int totalSum = 0;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                // Check if the length of the subarray is odd                if ((j - i + 1) % 2 != 0) {                    int currentSum = 0;                    // Calculate the sum of the current subarray                    for (int k = i; k <= j; k++) {                        currentSum += arr[k];                    }                    totalSum += currentSum;                }            }        }        return totalSum;    }}

Complexity

Time

O(n^3), where n is the number of elements in the array. The three nested loops lead to a cubic time complexity.

Space

O(1), as we only use a constant amount of extra space for variables like `totalSum` and `currentSum`.

Trade-offs

Pros

  • Very simple to understand and implement.

  • Directly follows the problem definition.

Cons

  • Extremely inefficient due to three nested loops.

  • Will result in a 'Time Limit Exceeded' error on larger inputs.

Solutions

class Solution {public  int sumOddLengthSubarrays(int[] arr) {    int n = arr.length;    int ans = 0;    for (int i = 0; i < n; ++i) {      int s = 0;      for (int j = i; j < n; ++j) {        s += arr[j];        if ((j - i + 1) % 2 == 1) {          ans += s;        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem