algoadvance

Leetcode 1588. Sum of All Odd Length Subarrays

Problem Statement

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.

Example:

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 58

Clarifying Questions

  1. Can the array contain duplicate elements?
    • Yes, the problem does not restrict duplicates in the array.
  2. What is the maximum length of the array arr?
    • The length of the array arr can go up to 100.
  3. Are all integers in the array guaranteed to be positive?
    • Yes, the problem specifies positive integers.

Strategy

  1. Brute Force Method:
    • Iterate over all possible subarrays.
    • Check if the length of the subarray is odd.
    • If the subarray length is odd, sum its elements and add it to the total sum.
  2. Optimized Method:
    • Instead of checking all possible subarrays which results in O(n^3) complexity, we can use the contribution of each element to the total sum of odd length subarrays.
    • For each element arr[i], determine the total number of subarrays in which it will appear.
    • Calculate the number of subarrays of each possible odd length that include arr[i].
    • Sum the contributions of each element.

Code

public class SumOfAllOddLengthSubarrays {
    public static int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            // Calculate the contribution of arr[i]
            int contribution = ((i + 1) * (n - i) + 1) / 2;
            sum += contribution * arr[i];
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 5, 3};
        System.out.println(sumOddLengthSubarrays(arr)); // Output: 58
    }
}

Time Complexity

The optimized method has a time complexity of:

Hence, the optimized approach will handle arrays even at their upper limit efficiently.

Summary

We leveraged a mathematical approach to determine the number of times an element contributes to various odd-length subarrays, reducing the need for nested loops and significantly optimizing the running time of our solution. This ensures our solution is scalable and efficient for the provided constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI