Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1588. Sum of All Odd Length Subarrays - Leetcode Solution

Code Implementation

class Solution:
    def sumOddLengthSubarrays(self, arr):
        total = 0
        n = len(arr)
        for i, num in enumerate(arr):
            # Number of subarrays where arr[i] is included
            left = i + 1
            right = n - i
            total_subarrays = left * right
            # Only count subarrays with odd length
            odd_count = (total_subarrays + 1) // 2
            total += num * odd_count
        return total
      
class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int total = 0, n = arr.size();
        for (int i = 0; i < n; ++i) {
            int left = i + 1;
            int right = n - i;
            int total_subarrays = left * right;
            int odd_count = (total_subarrays + 1) / 2;
            total += arr[i] * odd_count;
        }
        return total;
    }
};
      
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int total = 0, n = arr.length;
        for (int i = 0; i < n; ++i) {
            int left = i + 1;
            int right = n - i;
            int totalSubarrays = left * right;
            int oddCount = (totalSubarrays + 1) / 2;
            total += arr[i] * oddCount;
        }
        return total;
    }
}
      
var sumOddLengthSubarrays = function(arr) {
    let total = 0, n = arr.length;
    for (let i = 0; i < n; ++i) {
        let left = i + 1;
        let right = n - i;
        let totalSubarrays = left * right;
        let oddCount = Math.floor((totalSubarrays + 1) / 2);
        total += arr[i] * oddCount;
    }
    return total;
};

Problem Description

Given an array of positive integers arr, the task is to find the sum of all possible subarrays of arr that have an odd length. A subarray is a contiguous sequence of elements within the array. For each odd-length subarray, sum all its elements, and finally return the total sum across all such subarrays.
  • You must consider all subarrays whose lengths are odd (1, 3, 5, ... up to the array's length).
  • Each element can be used multiple times, as it may appear in several subarrays.
  • Constraints guarantee that arr will have at least one element and up to 100 elements, with values up to 1000.

Thought Process

The most straightforward way to solve this problem is to generate all possible subarrays, check if their length is odd, and then sum their elements. However, this brute-force approach is inefficient, especially as the array grows. We can optimize by finding a way to count how many times each element appears in odd-length subarrays, and then multiply the element by that count to get its contribution to the total sum. This avoids generating every subarray explicitly. The key insight is to count, for each element, the number of odd-length subarrays in which it appears. If we can do this efficiently, we can compute the answer in a single pass.

Solution Approach

To solve the problem efficiently, we use a combinatorial approach:
  1. For each element at index i in the array:
    • Count the number of subarrays that include arr[i].
    • For a given i, the number of choices to the left is i + 1 (including itself), and the number of choices to the right is n - i (including itself).
    • So, there are (i + 1) * (n - i) subarrays that include arr[i].
  2. Not all of these subarrays are of odd length. Since subarrays can start and end at different places, about half of the subarrays containing arr[i] will be of odd length. Specifically, for each element, the number of odd-length subarrays it appears in is ((i + 1) * (n - i) + 1) // 2.
  3. Multiply arr[i] by the number of odd-length subarrays it appears in, and add to the total sum.
  4. Repeat for all elements and sum the results.
This approach ensures that we process each element only once and avoid redundant calculations.

Example Walkthrough

Let's take arr = [1,4,2,5,3] as an example.
  • For arr[0] = 1:
    • Left choices: 1, Right choices: 5
    • Total subarrays: 1 * 5 = 5
    • Odd subarrays: (5 + 1) // 2 = 3
    • Contribution: 1 * 3 = 3
  • For arr[1] = 4:
    • Left: 2, Right: 4, Subarrays: 8, Odd: (8+1)//2 = 4, Contribution: 4*4 = 16
  • For arr[2] = 2:
    • Left: 3, Right: 3, Subarrays: 9, Odd: (9+1)//2 = 5, Contribution: 2*5 = 10
  • For arr[3] = 5:
    • Left: 4, Right: 2, Subarrays: 8, Odd: (8+1)//2 = 4, Contribution: 5*4 = 20
  • For arr[4] = 3:
    • Left: 5, Right: 1, Subarrays: 5, Odd: (5+1)//2 = 3, Contribution: 3*3 = 9
Summing contributions: 3 + 16 + 10 + 20 + 9 = 58, which matches the expected answer.

Time and Space Complexity

  • Brute-force:
    • Time Complexity: O(n3), because for each subarray (O(n2)), we sum all elements (O(n)).
    • Space Complexity: O(1), if not storing subarrays explicitly.
  • Optimized approach (as above):
    • Time Complexity: O(n), since we process each element once.
    • Space Complexity: O(1), only a few variables are used.
The optimized approach is efficient and suitable for the problem's constraints.

Summary

The essence of this problem is counting how many times each element appears in odd-length subarrays and summing their contributions. By recognizing the pattern and using combinatorics, we avoid unnecessary computation and achieve an elegant, efficient solution that works for all input sizes within the constraints.