Given an array of size N and a number K. We have to find the sub-array of size K such that the sum of it’s elements is minimum among all K-size sub arrays.
For example Let us consider the following array of size 10.
{1, 2, 1, 3, 1, 1, 1, 4, 2, 3}
The smallest sub-array of size 3 is {1, 1, 1} which starts at the index 4 (0-based index).
We can use the following algorithm.
We calculate the sum of first K numbers initially and assume that this is the minimum sum and the index is 0. We maintain a variable to track the running sum of K values.
When we move the sliding window by one element, we subtract the previous element add the current element to the running sum. Then we update the minimum sum if the latest sum is less than minimum sum.
This procedure is repeated till the sliding window reaches the end of the array.
Here is the C++ implementation.