Sum of all subarrays of size K

Given an array arr[]
and an integer K
, the task is to calculate the sum of all subarrays of size K.

Examples:

Input:arr[] = {1, 2, 3, 4, 5, 6}, K = 3

Output:6 9 12 15

Explanation:

All subarrays of size k and their sum:

Subarray 1: {1, 2, 3} = 1 + 2 + 3 = 6

Subarray 2: {2, 3, 4} = 2 + 3 + 4 = 9

Subarray 3: {1, 2, 3} = 3 + 4 + 5 = 12

Subarray 4: {1, 2, 3} = 4 + 5 + 6 = 15

Input:arr[] = {1, -2, 3, -4, 5, 6}, K = 2

Output:-1, 1, -1, 1, 11

Explanation:

All subarrays of size K and their sum:

Subarray 1: {1, -2} = 1 – 2 = -1

Subarray 2: {-2, 3} = -2 + 3 = -1

Subarray 3: {3, 4} = 3 – 4 = -1

Subarray 4: {-4, 5} = -4 + 5 = 1

Subarray 5: {5, 6} = 5 + 6 = 11

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive Approach:The naive approach will be to generate all subarrays
of size K
and find the sum of each subarray using iteration.

Below is the implementation of the above approach:

C/C++

filter_none

edit

close

play_arrow

brightness_4

code

`// C++ implementaion to find the sum`
`// of all subarrays of size K`
` `
`#include <iostream>`
`using`
`namespace`
`std;`
` `
`// Function to find the sum of `
`// all subarrays of size K`
`int`
`calcSum(`
`int`
`arr[],`
`int`
`n,`
`int`
`k)`
`{`
` `
`  `
`// Loop to consider every `
`  `
`// subarray of size K`
`  `
`for`
`(`
`int`
`i = 0; i <= n - k; i++) {`
`  `
`  `
`// Initialize sum = 0`
`  `
`int`
`sum = 0;`
` `
`  `
`// Calculate sum of all elements`
`  `
`// of current subarray`
`  `
`for`
`(`
`int`
`j = i; j < k + i; j++)`
`  `
`sum += arr[j];`
` `
`  `
`// Print sum of each subarray`
`  `
`cout << sum <<`
`" "`
`;`
`  `
`}`
`}`
` `
`// Driver Code`
`int`
`main()`
`{`
`  `
`int`
`arr[] = { 1, 2, 3, 4, 5, 6 };`
`  `
`int`
`n =`
`sizeof`
`(arr) /`
`sizeof`
`(arr[0]);`
`  `
`int`
`k = 3;`
` `
`  `
`// Function Call`
`  `
`calcSum(arr, n, k);`
` `
`  `
`return`
`0;`
`}`

chevron_right

filter_none

Output:

Performance Analysis:

• Time Complexity:
As in the above approach, There are two loops, where first loop runs (N – K) times and second loop runs for K times. Hence the Time Complexity will be O(N*K)
.
• Auxiliary Space Complexity:
As in the above approach, There is no extra space used. Hence the auxiliary space complexity will be O(1)
.

Effiecient Approach: Using Sliding Window

The idea is to use thesliding window approach to find the sum of all possible subarrays in the array.

• For each size in the range [0, K], find the sum of the first window of size K and store it in an array.
• Then for each size in the range [K, N], add the next element which contributes into the sliding window and subtract the element which pops out from the window.

```// Adding the element which
// adds into the new window
sum = sum + arr[j]
// Subtracting the element which
// pops out from the window
sum = sum - arr[j-k]
where sum is the variable to store the result
arr is the given array
j is the loop variable in range [K, N]```

Below is the implementation of the above approach:

C/C++

filter_none

edit

close

play_arrow

brightness_4

code

`// C++ implementaion to find the sum`
`// of all subarrays of size K`
` `
`#include <iostream>`
`using`
`namespace`
`std;`
` `
`// Function to find the sum of `
`// all subarrays of size K`
`int`
`calcSum(`
`int`
`arr[],`
`int`
`n,`
`int`
`k)`
`{`
`  `
`// Initialize sum = 0`
`  `
`int`
`sum = 0;`
` `
`  `
`// Consider first subarray of size k`
`  `
`// Store the sum of elements`
`  `
`for`
`(`
`int`
`i = 0; i < k; i++)`
`  `
`sum += arr[i];`
` `
`  `
`// Print the current sum`
`  `
`cout << sum <<`
`" "`
`;`
` `
`  `
`// Consider every subarray of size k`
`  `
`// Remove first element and add current`
`  `
`// element to the window`
`  `
`for`
`(`
`int`
`i = k; i < n; i++) {`
`  `
`  `
`// Add the element which enters`
`  `
`// into the window and substract`
`  `
`// the element which pops out from`
`  `
`// the window of the size K`
`  `
`sum = (sum - arr[i - k]) + arr[i];`
`  `
`  `
`// Print the sum of subarray`
`  `
`cout << sum <<`
`" "`
`;`
`  `
`}`
`}`
` `
`// Drivers Code`
`int`
`main()`
`{`
`  `
`int`
`arr[] = { 1, 2, 3, 4, 5, 6 };`
`  `
`int`
`n =`
`sizeof`
`(arr) /`
`sizeof`
`(arr[0]);`
`  `
`int`
`k = 3;`
`  `
`  `
`// Function Call`
`  `
`calcSum(arr, n, k);`
` `
`  `
`return`
`0;`
`}`

chevron_right

filter_none

Output:

Performance Analysis:

• Time Complexity:
As in the above approach, There is one loop which take O(N) time. Hence the Time Complexity will be O(N)
.
• Auxiliary Space Complexity:
As in the above approach, There is no extra space used. Hence the auxiliary space complexity will be O(1)
.

My Personal Notes

arrow_drop_up