1588 - Sum Of All Odd Length Subarrays (Easy)
Problem Link
https://leetcode.com/problems/sum-of-all-odd-length-subarrays/
Problem Statement
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 <= 1001 <= arr[i] <= 1000
Follow up:
Could you solve this problem in time complexity?
Approach 1: Brute Force
For a brute force solution, we generate every subarray with odd length and sum all its members. Starting from the position one, we and sum all subarray of odd length that starts in the current position. We repeat this process to all positions.
- Java
- Rust
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int totalSum = 0;
for (int startingPosition = 0; startingPosition < arr.length; startingPosition++) {
for (int length = 1; length + startingPosition - 1 < arr.length; length += 2) {
for (int numberToSum = startingPosition; numberToSum < startingPosition + length; numberToSum++) {
totalSum += arr[numberToSum];
}
}
}
return totalSum;
}
}
impl Solution {
pub fn sum_odd_length_subarrays(arr: Vec<i32>) -> i32 {
let n = arr.len();
let mut ans = 0;
for i in (1..=n).step_by(2) {
for w in arr.windows(i) {
ans += w.iter().sum::<i32>();
}
}
ans
}
}
Time Complexity:
Iterating over the starting positions is .
For each position, we iterate over the sizes of odd subarrays that can start on that position:
For each subarray, we need to iterate over its items to sum the values:
As each of the processes stated above are nested into each other the total complexity is .
Space Complexity:
The only extra memory we are using is the result sum.
Approach 2: Sliding Window
The second approach uses a sliding window. We can create a window of each odd size that fits the array and move the window removing the value of the first element and adding the value of the next element. With this approach we save an extra loop avoiding to calculate the window from scratch every time.
- Java
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int totalSum = 0;
for (int windowSize = 1; windowSize <= arr.length; window += 2) {
int windowSum = 0;
// calculate the sum of the window with one element missing
for (int index = 0; index < windowSize - 1; index++) {
windowSum += arr[index];
}
// loop invariant: windowSum is always 1 element short
for (int index = windowSize - 1; index < arr.length; index++) {
// add the missing element
windowSum += arr[index];
totalSum += window;
// remove the first element
windowSum -= arr[index - (windowSize - 1)];
}
}
return totalSum;
}
}
Time Complexity:
Possible sizes of odd windows: .
Calculate window without the last element: .
Slide the window until the end of the array: .
As we only need to calculate the widow once for each size and then slide the complexity would be .
Space Complexity:
The only extra memory we are using is the result sum and another one for the window sum.
Approach 3: Calculate the number of subarrays and element is present.
Things gets a bit tricky when we think about the follow up question: Can we make it O(n)?
The idea to try to make this O(n) is to calculate the number of subarrays a single element would be present. If we can calculate that then we just need to iterate over the array once summing the current element times the number of subarrays it is present.
Let's forget for a bit the fact that we are only interested in odd-length subarrays. The total number of subarrays and element is present can be calculated with the following formula:
(element position + 1) * (number of elements - element position)
To visualize that we can create a table representing the subarrays. In the columns we have the index of the last element in the subarray and in the rows we have the first element of the subarray. Let's create that table for an array of size 8 and fulfill the table to calculate the number of subarrays the element in position 2 appears. An empty cell means impossible subarray (ending before it starts), f means element in position 3 is not present and t means it is present.
|0|1|2|3|4|5|6|7
0|f|f|t|t|t|t|t|t
1| |f|t|t|t|t|t|t
2| | |t|t|t|t|t|t
3| | | |f|f|f|f|f
4| | | | |f|f|f|f
5| | | | | |f|f|f
6| | | | | | |f|f
6| | | | | | | |f
As we can observe, the ts formed a rectangle with sides position of the element plus 1 and number of elements minus the position of the element.
As we are only interested in the odd-length arrays, we can divide this number by two rounding up. When the number of subarrays is odd, we know that there is one more odd-length than even-length subarrays, eg: 7 subarrays => 3 even-length and 4 odd-length.
- Java
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int totalSum = 0;
for (int index = 0; index < arr.length; index++) {
int totalOfSubArrays = (index + 1) * (arr.length - i);
// summing the rest of the division to round up
totalSum += (totalOfSubArrays / 2 + totalOfSubArrays % 2) * arr[i];
}
return totalSum;
}
}
Time Complexity:
Access each element of the array and calculate the number of subarrays for each: .
Space Complexity:
The only extra memory we are using is the result sum and another one for the window sum.