Skip to content

1588. Sum of All Odd Length Subarrays 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int sumOddLengthSubarrays(vector<int>& arr) {
    int ans = 0;
    // Maintain two sums of subarrays ending in the previous index.
    // Each time we meet a new number, we'll consider "how many times" it should
    // contribute to the newly built subarrays by calculating the number of
    // previous even/odd-length subarrays.
    int prevEvenSum = 0;  // the sum of even-length subarrays
    int prevOddSum = 0;   // the sum of odd-length subarrays

    for (int i = 0; i < arr.size(); ++i) {
      // (i + 1) / 2 := the number of previous odd-length subarrays.
      const int currEvenSum = prevOddSum + ((i + 1) / 2) * arr[i];
      // i / 2 + 1 := the number of previous even-length subarrays
      // (including 0).
      const int currOddSum = prevEvenSum + (i / 2 + 1) * arr[i];
      ans += currOddSum;
      prevEvenSum = currEvenSum;
      prevOddSum = currOddSum;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int sumOddLengthSubarrays(int[] arr) {
    int ans = 0;
    // Maintain two sums of subarrays ending in the previous index.
    // Each time we meet a new number, we'll consider "how many times" it should
    // contribute to the newly built subarrays by calculating the number of
    // previous even/odd-length subarrays.
    int prevEvenSum = 0; // the sum of even-length subarrays
    int prevOddSum = 0;  // the sum of odd-length subarrays

    for (int i = 0; i < arr.length; ++i) {
      // (i + 1) / 2 := the number of previous odd-length subarrays.
      final int currEvenSum = prevOddSum + ((i + 1) / 2) * arr[i];
      // i / 2 + 1 := the number of previous even-length subarrays
      // (including 0).
      final int currOddSum = prevEvenSum + (i / 2 + 1) * arr[i];
      ans += currOddSum;
      prevEvenSum = currEvenSum;
      prevOddSum = currOddSum;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def sumOddLengthSubarrays(self, arr: List[int]) -> int:
    ans = 0
    # Maintain two sums of subarrays ending in the previous index.
    # Each time we meet a new number, we'll consider 'how many times' it should
    # contribute to the newly built subarrays by calculating the number of
    # previous even/odd-length subarrays.
    prevEvenSum = 0  # the sum of even-length subarrays
    prevOddSum = 0  # the sum of odd-length subarrays

    for i, a in enumerate(arr):
      # (i + 1) // 2 := the number of previous odd-length subarrays.
      currEvenSum = prevOddSum + ((i + 1) // 2) * a
      # i // 2 + 1 := the number of previous even-length subarrays
      # (including 0).
      currOddSum = prevEvenSum + (i // 2 + 1) * a
      ans += currOddSum
      prevEvenSum = currEvenSum
      prevOddSum = currOddSum

    return ans