Leetcode – Sum of All Odd Length Subarrays Solution

Spread the love

Array manipulation and subarray problems are an integral part of any competitive programming environment, be it Leetcode, HackerRank, or technical interviews. Understanding how to handle subarrays can provide crucial insights into solving complex problems that involve sequences and structures. The problem “Sum of All Odd Length Subarrays” from Leetcode serves as a wonderful introduction to this domain, providing a challenge that can be solved using multiple algorithms, ranging from brute force to optimized techniques.

In this article, we will delve deep into the problem’s intricacies, evaluate various approaches to solving it, and implement these solutions in Python. We will also analyze the performance of each algorithm in terms of time and space complexity.

Problem Statement

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays. A subarray is a contiguous subsequence of the array. Return the sum of all odd-length subarrays of arr.

Constraints

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

Example

For arr = [1, 4, 2, 5, 3], the odd-length subarrays are [1], [4], [2], [5], [3], [1,4,2], [4,2,5], [2,5,3], [1,4,2,5,3], and their sums are 1+4+2+5+3+7+11+10+15 = 58.

Naive Approach: Brute-Force

Algorithm

  1. Initialize a variable total_sum to zero.
  2. Loop through the array, creating all possible odd-length subarrays.
  3. Calculate the sum of each subarray and add it to total_sum.

Python Implementation

def sumOddLengthSubarrays(arr):
    total_sum = 0
    n = len(arr)
    
    for i in range(n):
        for j in range(i, n, 2):  # 2nd loop iteration step is 2 to get odd-length subarrays
            total_sum += sum(arr[i:j+1])
            
    return total_sum

Time Complexity

The time complexity of this approach is O(n^3).

Space Complexity

The space complexity is O(1).

Optimized Approach: Mathematical Insight

Algorithm

  1. Recognize that each element arr[i] will appear in the final sum exactly ((i + 1) * (n - i) + 1) // 2 times.
  2. Initialize a variable total_sum to zero.
  3. Loop through the array, adding arr[i] * ((i + 1) * (n - i) + 1) // 2 to total_sum.

Python Implementation

def sumOddLengthSubarrays(arr):
    total_sum = 0
    n = len(arr)
    
    for i in range(n):
        total_sum += arr[i] * ((i + 1) * (n - i) + 1) // 2
    
    return total_sum

Time Complexity

The time complexity is O(n).

Space Complexity

The space complexity is O(1).

Comparison of Approaches

Conclusion

The “Sum of All Odd Length Subarrays” problem is a fascinating example that teaches you the power of mathematical insights in algorithmic problem solving. While the brute-force approach is relatively straightforward to implement, it quickly becomes impractical for larger arrays due to its cubic time complexity. The optimized approach leverages the power of mathematical patterns to bring down the time complexity to linear time, making it an ideal choice for this problem.

Leave a Reply