Given a list of numbers arr
and an integer k
, slide a window of size k across the array, and return an array containing the sum at each position of the window.
Example:
Explanation:
One way to solve this problem is to use a brute-force approach.
To do this, you can simply slide a window across the Array, computing the sum of all the elements each time.
Time Complexity O(n⋅k). We loop over every element. For every iteration in the loop, we sum k elements together. This gives O(n * k) time.
Space Complexity O(n−k). The ans array has n - k
total elements in it.
The above solution is very slow because you have to compute the sum every time, which takes O(k) operations each time.
To solve this problem efficiently, each time you slide the window, you can add 1 new element to the sum, remove 1 old element from the sum, like this:
When you do this, it takes 2 operations, which is a total of O(2) = O(1) operations. This is much faster than before, which took O(k) operations.
Here's the code for doing this:
Time Complexity O(n). We loop over the entire array. Each iteration takes O(1) time.
Space Complexity O(n−k). The solution contains n - k - 1 elements.